Aplicații ale teoriei graficului
Graficele planare
Se spune că un grafic G este plan dacă poate fi reprezentat pe un plan într-o asemenea manieră încât vârfurile sunt puncte distincte, marginile sunt curbe simple și nici două muchii nu se întâlnesc unele cu altele decât la terminalele lor. De exemplu, K 4, graficul complet pe patru vârfuri, este plan, așa cum arată figura 4A.
Se spune că două grafice sunt homeomorfe dacă ambele pot fi obținute din același grafic prin subdiviziuni ale muchiilor. De exemplu, graficele din Figura 4A și Figura 4B sunt homeomorfe.
Graficul K m, n este un grafic pentru care setul de vertexuri poate fi împărțit în două subseturi, unul cu vârfuri m și celălalt cu n vârfuri. Orice două vârfuri ale aceluiași subset sunt neadiacente, în timp ce oricare două vârfuri ale subseturilor diferite sunt adiacente. Matematicianul polonez Kazimierz Kuratowski în 1930 a dovedit următoarea teoremă celebră:
O condiție necesară și suficientă pentru un grafic G să fie plană este că aceasta nu conține un homeomorf subgrafic fie K 5 sau K 3,3 prezentat în figura 5.
O contracție elementară a unui grafic G este o transformare a lui G într-un nou grafic G 1, astfel încât două vârfuri adiacente u și υ de G sunt înlocuite cu un nou vertex w în G 1 și w este adiacent în G 1 la toate vârfurile la care fie u sau υ sunt adiacente în G. Un grafic G * se spune că este o contracție a lui G dacă G * poate fi obținut din G printr-o secvență de contracții elementare. Următoarea este o altă caracterizare a unui grafic plan datorită matematicianului german K. Wagner în 1937.
Un grafic este planar dacă și numai dacă nu este contractibil cu K 5 sau K 3,3.
Problema hărții în patru culori
Timp de mai bine de un secol, soluția problemei hărții în patru culori a evadat fiecare analist care a încercat-o. Problema poate că a atras atenția lui Möbius, dar prima referire scrisă la aceasta pare să fie o scrisoare de la un Francis Guthrie către fratele său, un student al lui Augustus De Morgan, în 1852.
Problema se referă la hărți plane - adică subdiviziuni ale avionului în regiuni neaprapuse delimitate prin simple curbe închise. În hărțile geografice s-a observat empiric, în câte cazuri speciale s-au încercat, încât, cel mult, patru culori sunt necesare pentru a colora regiunile, astfel încât două regiuni care au o frontieră comună să fie întotdeauna colorate diferit și în anumite cazuri în care sunt necesare cel puțin patru culori. (Regiunile care se întâlnesc doar la un moment dat, cum ar fi statele Colorado și Arizona din Statele Unite, nu sunt considerate a avea o frontieră comună). O formalizare a acestei observații empirice constituie ceea ce se numește „teorema în patru culori”. Problema constă în dovedirea sau respingerea afirmației că acesta este cazul pentru fiecare hartă plană. Că trei culori nu vor fi suficiente este ușor de demonstrat, în timp ce suficiența a cinci culori a fost dovedită în 1890 de matematicianul britanic PJ Heawood.
În 1879 AB Kempe, un englez, a propus o soluție a problemei în patru culori. Deși Heawood a arătat că argumentul lui Kempe a fost defect, două dintre concepțiile sale s-au dovedit fructuoase în anchetele ulterioare. Una dintre acestea, numită inevitabilitate, afirmă corect imposibilitatea construirii unei hărți în care fiecare din cele patru configurații este absentă (aceste configurații constau dintr-o regiune cu doi vecini, una cu trei, una cu patru și una cu cinci). Al doilea concept, cel al reducibilității, își ia numele de la dovada valabilă a lui Kempe că, dacă există o hartă care necesită cel puțin cinci culori și care conține o regiune cu patru (sau trei sau doi) vecini, atunci trebuie să existe o hartă care să necesite cinci culori pentru un număr mai mic de regiuni. Încercarea lui Kempe de a demonstra reducibilitatea unei hărți care conține o regiune cu cinci vecini a fost eronată, dar a fost rectificată într-o dovadă publicată în 1976 de Kenneth Appel și Wolfgang Haken din Statele Unite. Dovada lor a atras unele critici deoarece a necesitat evaluarea a 1.936 de cazuri distincte, fiecare implicând până la 500.000 de operații logice. Appel, Haken și colaboratorii lor au conceput programe care au făcut posibil ca un computer digital mare să se ocupe de aceste detalii. Calculatorul a necesitat mai mult de 1.000 de ore pentru a efectua sarcina, iar dovada formală rezultată este lungă de câteva sute de pagini.
Ciclurile euleriene și problema podului Königsberg
Un G multigraf constă dintr-un set V (G) ne-gol de vârfuri și un subset E (G) din mulțimea de perechi neordonate de elemente distincte de V (G) cu o frecvență f ≥ 1 atașată la fiecare pereche. Dacă perechea (x 1, x 2) cu frecvența f aparține E (G), atunci vertexurile x 1 și x 2 sunt unite de marginile f.
Un ciclu Eulerian al unui G multigraf este un lanț închis în care fiecare muchie apare exact o dată. Euler a arătat că un multigraf posedă un ciclu Eulerian dacă și numai dacă este conectat (în afară de punctele izolate) și numărul de vârfuri de grad impar este fie zero sau două.
Această problemă a apărut mai întâi în felul următor. Râul Pregel, format prin confluența celor două ramuri ale sale, străbate orașul Königsberg și se varsă pe ambele părți ale insulei Kneiphof. Au fost șapte poduri, așa cum se arată în figura 6A. Orășenii s-au întrebat dacă este posibil să meargă la plimbare și să traverseze fiecare pod o singură dată. Acest lucru este echivalent cu găsirea unui ciclu eulerian pentru multigraful din figura 6B. Euler a arătat că este imposibil, deoarece există patru vârfuri de ordine ciudată.
