Guthrie

Problema Guthrie (problema celor patru culori) Aceasta problema a fost formulata in octombrie 1852 de catre Francisc Guthrie. In timp ce colora o harta Guthrie a observat ca indiferent cat de complicata ar aceasta, numarul de culori necesare colorarii hartii astfel incat toate poligoanele adiacente sa aiba culori diferite este patru. Aceasta conjectura a lui Guthrie a ramas nedemonstrata pana in anul 1976 cand, doi matematicieni de la Universitatea Illinois, Wolfgang Haken si Kenneth Appel au reusit sa programeze un calculator care a demonstrat (prin mii de ore de calcul si sute de pagini ) demonstrarea conjecturii. In cele ce urmeaza voi prezenta o abordare proprie a problemei celor patru culori, abordare in care ma bazez in principal pe formula lui Euler pentru retele plane. Demonstratia mea se imparte in doua etape, una de demonstratie in teoria retelelor iar partea nala se refera la transpunerea problemei in teora retelelor. Scop principal: O retea de cinci puncte in care ecare nod este conectat cu toate celelalte printr-o ramura poate exista daca si numai daca cel putin doua ramuri se intersecteaza cel putin intr-un punct (care nu este nod). I. Fie o retea de doua noduri (A si B) si doua ramuri (curbe continue C1 C2). Conform formulei lui Euler reteaua include un singur domeniu. Formula lui Euler pentru retele plane : N+D-R=1 (N=numarul de noduri; D=numarul domeniilor; R=numarul ramurilor) Numim contur al retelei curba continua care include toate subdomeniile retelei. Fie C3 o noua ramura a retelei trasata prin exteriorul acesteia. Conform formulei lui euler, pentru o retea de doua noduri si trei ramuri reteaua include doua subdomenii ( marginite de cele trei curbe). Numarul de ramuri pe care le poate avea un subdomeniu ( care poate considerat o retea de sine statatoare) este dat tot de formula lui Euler pentru o retea cu doua noduri si un domeniu, astfel doua si numai doua laturi delimiteaza ecare subdomeniu. (Obs. Conturul retelei reprezinta o reuniune de subdomenii care face abstractie de delimtarile interne ale acestora, asadar numarul de ramuri ale conturului este calculabil prin formula lui Euler considerand numarul de domanii incluse ca nd 1) Asadar pentru o retea de doua noduri cu indiferent cate ramuri care unesc nodurile, conturul va format de doua si numai doua ramuri. O ramura poate sa nu apartina nici conturului nici interiorului retelei doar daca nu delimiteaza nici un sub-domeniu (ceea ce in cazul de fata nu se poate intampla, toate ramurile delimitand cel putin un domeniu) Ca un corolar se poate a rma ca intr-o retea cu doua noduri si trei ramuri o ramura si numai una este inclusa in interiorul retelei (i.e. toate punctele de pe acea ramura, cu exceptia nodurilor, sunt interioare retelei si deci nu apartin exteriorului). II. Fie patru noduri A, B, C, D, noduri intr-o retea cu laturile AB AC AD BC BD CD. Sa analizam arborele format din ramurile AB-BC-CD-DA. Observam ca arborele formeaza un contur continuu ( inclusiv in noduri) si este in acelasi timp si conturul retelei. Caz 1: Fie BD ramura a retelei inclusa in interiorul conturului ABCD; In acest caz domeniul retelei nou formate este impartit in doua si numai doua sub-domenii : ABD si DAC. Este evident ca singurele puncte comune intre cele doua sub-domenii sunt cele care apartin ramurii BC. Fie AC ramura a retelei inclusa in interiorul conturului ABCD. Fie X un punct oarecare pe ramura AC inclus in subdomeniul BCD (sau ABD ) asadar segmentul XC din ramura AC este inclusa in domeniul BCD. Insa punctul A nu apartine domeniului BCD, asadar ramura AC va trebui sa aiba cel putin inca un segment* care nu este inclus in domeniul BCD (asadar exterior domeniului BCD). * (segment si nu punct deoarece daca restrangeam enuntul la un singur punct, acesta ar trebuit sa e chiar nodul A, nod care este strct exterior conturului BCD). In continuare, daca ramura AC are un segment in interiorul conturului BCD si alt segment in exteriorul conturului continu BCD, atunci in mod cert AC intersecteaza cel putin odata cel putin o ramura care alcatuieste conturul BCD (deoarece BC-CD-DB formeaza un contur continuu inchis).

Concluzionam de aici ca AC nu poate sa apartina interiorului arborelui ABCD. AC nu poate apartine nici conturului arborelui deoarece ar intersecta o in nitate de puncte ale ramurilor acestuia. Exemplu cu o solutie in care AC este exteior ABCD. Asadar daca AC exista si nu intersecteaza nici o alta ramura este strict exteriorarborelu ABCD. Observam ca AB-BC si ADDC sunt curbe continue (deoarece am presupus ca ramurile sunt continue avand nodul in comun) Caz 2: Presupunem ca BC este o ramaura care apartine strict exteriorului arborelui ABCD. Conform lui Euler, reteaua nou formata este alcatuita din doua sub-domenii dintre care cumoastem ca unul este ABCD iar celuilalt ii cunoastem una din laturi. Cunoastem insa ca BAAD si BC-CD sunt curbe continue (deoarece am presupus ca ramurile sunt continue avand nodul in comun) Asadar atat in cazul 1 cat si in cazul 2, exista trei curbe continue care unesc doua noduri. Astfel putem concluziona ca exista o curba si numai una care are toate punctele incluse in interiorul retelei (exceptand nodurile); Din ipoteze insa, atat in cazul 1 cat si in cazul 2 curba "directa" este demonstrata, respectiv presupusa, ca neapartinand interiorului (apartinand chiar conturului retelei). Asadar acea curba interioara trebuie sa e una "indirecta" (prin "indirecta" intelegem o curba continua formata de doua ramuri ex: AC-CD) Avand in vedere ca latura "indirecta" contine trei noduri (dintre care numai doua nu apartin strict interiorului retelei) conchidem ca in ambele cazuri exista un nod si numai unul inclus strict in interiorul retelei (strict in sensul ca el nu poate sa apartina conturului retelei). III. Orice retea de patru puncte cu sase laturi, conform formulei lui Euler, este impartita in strict trei subdomenii care au in comun numai ramuri ale retelei (i.e. nici un subdomeniu nu include un alt subdomeniu). Presupunem ca nodul continut in interiorul retelei este nodul A. Toate nodurile ramase: B,C si D trebuie sa se gaseasca pe conturul retelei. Aceste noduri genereaza un singur contur continu: BC-CD-DB care este si conturul retelei. Analizand un subdomeniu (ales intamplator) ABC, observam ca nodul D nu apartine conturului ABC; in plus, D nu apartine nici interiorului ABC, aceasta deoarece domeniul ABC este inclus in DBC, iar daca D ar inclus in ABC atunci si DBC ar inclus in ABC, aceasta dubla incluziune conducand la conditia de identitate intre ABC si DBC (lucru fals deoarece ABD si ACD exista ca subdomenii nenule). Asadar D apartine strict exteriorului conturului ABC. IV. Fie o retea ABCD (similatra cu cea analizata mai sus) si un alt nod E. i) Daca E apartine exteriorului retelei atunci ramura AE ar trebui sa apartina simultan exteriorului si interiorului retelei, acest fapt ar conduce la intersectarea ramurii AE cu conturul continu BC-CD-DB. ii) Daca E apartine interiorului retelei atunci el apartine in mod evident unui subdomeniu (ex. AB-BC-CA) continu care exclude un nod (ex. nodul D) , asadar ramura respectiva (ex. ED) ar apartine simultan interiorului si exteriorului sub-domeniului respectiv (ceea ce conduce la intersectia ramurii cu conturul domeniului). Concluzionam ca intr-o retea de cinci noduri si zece ramuri exista cel putin doua ramuri care se intersecteaza cel putin odata. Modelarea problemei Guthrie in forma unei retele de cinci puncte: Scop: Demonstrarea imposibilitatii conectarii simultana si reciproca a cinci regiuni plane. Pentru a demonstra ca teorema Guthrie este adevarata, trebuie aratat ca este imposibila conectarea simultana si reciproca a mai mult de patru regiuni din plan. Demonstrarea imposibilitatii conectarii a cinci regiuni in plan echivaleaza cu demonstraea imposibilitatii conectarii a mai mult de patru regiuni din plan. Presupunem cinci domenii plane : A,B,C,D si E, care nu sunt conectate unul cu celalalt prin nici o linie de demarcatie(frontiera). Sa presupunem acum o serie de 10 regiuni plane, numite "punti" care unesc doua cate doua domeniile A,B,C,D si E. Pentru a putea modela domenile A,B,C,D,E si "puntile" cu noduri ale unei retele si respectiv cu ramurile retelei, este nevoie de cateva reguli minimale de transformare (N.B. regulile sunt MINIMALE, urmarea lor este necesara dar nu su cienta pentru a valida modelarea)

Reguli minimale pentru transformare 1. Doua punti nu pot sa se intersecteze. Acest fapt ar conduce la intreruperea uneia dintre ele sau a amandurora. (din ipoteza de lucu, o regiune plana nu poate apartine simultan de doua domenii diferite) 1* Un domeniu nu poate sa e in contact cu o punte care il conecteaza de un alt domeniu de care este deja conectat ( teoretic pot exista oricate punti intre doua domenii insa necesara este numai una singura) 2. Nici o regiune, e ea domeniu sau "punte", nu poate inclusa in totalitate in nici o alta regiune( e ea domeniu sau "punte"). Aceasta deoarece printr-o asemenea incluziune, domeniul inclus va izolat de accesul la un alt domeniu. Observam ca daca modelam problema Guthrie dupa aceste reguli minimale obtinem o retea care neaga cel putin una dintre ele: pentru ca o asemenea retea sa existe, cel putin doua ramuri se vor intersecta in cel putin un loc ( incalcand prima regula minimala) Concluzionam ca cinci regiuni plane nu pot conectate simultan reciproc. Ceea ce conduce la inutilitatea folosirii a cinci mijloace de identi care (cromatice) diferite. Stud. Ing. Aerospatiala Valeriu Dragan 1 dec.2006