Teoria grafurilor
Puncte și linii între ele: asta e tot ce înseamnă un graf. Totuși, același desen descrie o hartă rutieră, o rețea de prieteni, o moleculă și internetul, iar întrebările pe care le puteți pune despre el, de la numărul de culori de care are nevoie până la posibilitatea de a-l trasa dintr-o singură linie, îi țin ocupați pe matematicieni încă din 1736.
Vârfuri și muchii
Un graf are vârfuri, numite și noduri, și muchii, fiecare unind două vârfuri. Nu contează unde sunt desenate vârfurile, ci doar care perechi sunt unite, așa că același graf poate arăta foarte diferit pe hârtie. Grafurile din laborator sunt simple: nicio muchie nu leagă un vârf de el însuși și între două vârfuri există cel mult o muchie. Cu n vârfuri pot exista cel mult n(n − 1) / 2 muchii; un graf care le are pe toate se numește complet, iar K5 este graful complet cu cinci vârfuri.
Gradele și lema strângerilor de mână
Gradul unui vârf este numărul de muchii care pornesc din el. Adunați toate gradele și veți obține exact dublul numărului de muchii, pentru că fiecare muchie are două capete și este numărată o dată la fiecare. Aceasta este lema strângerilor de mână: în orice grup, strângerile de mână numărate persoană cu persoană dau împreună dublul numărului de strângeri de mână. De aici rezultă și că numărul vârfurilor cu grad impar este întotdeauna par. Un graf în care toate vârfurile au același grad k se numește k-regulat.
Grafuri conexe, arbori și cicluri
Un graf este conex când din orice vârf se poate ajunge în oricare altul de-a lungul muchiilor; altfel se desface în bucăți, numite componente conexe. Un ciclu este un traseu închis care revine la punctul de plecare fără să treacă de două ori prin același vârf, iar lungimea celui mai scurt ciclu este talia grafului. Un graf conex fără cicluri este un arbore, iar un arbore cu n vârfuri are întotdeauna exact n − 1 muchii: cu una mai puțin se desface, cu una mai mult are un ciclu. Orice graf conex conține un arbore parțial, adică un arbore care atinge toate vârfurile folosind doar o parte din muchii.
Grafuri bipartite și colorare
Colorați vârfurile astfel încât nicio muchie să nu unească două vârfuri de aceeași culoare. Cel mai mic număr de culori cu care se poate face asta este numărul cromatic. O singură culoare ajunge doar dacă nu există muchii. Două culori ajung exact atunci când graful este bipartit: vârfurile sale se împart în două părți și fiecare muchie trece de la o parte la cealaltă. Dénes Kőnig a arătat în 1936 că asta este același lucru cu a nu avea niciun ciclu de lungime impară, pentru că pe un ciclu impar două culori nu pot alterna. Pentru trei sau mai multe culori nu se cunoaște un test atât de simplu: a decide dacă trei culori ajung este o problemă NP-completă, așa că programele caută soluția, la fel ca laboratorul.
Un exemplu: graful Petersen
Luați un pentagon A–B–C–D–E și o stea cu cinci colțuri F–H–J–G–I în interiorul lui și uniți fiecare colț al pentagonului cu un vârf al stelei: A–F, B–G, C–H, D–I și E–J. Acesta este graful Petersen, cu 10 vârfuri și 15 muchii. Fiecare vârf are gradul 3, deci suma gradelor este 30, dublul lui 15. Cel mai scurt ciclu are lungimea 5, deci graful nu are triunghiuri, dar pentagonul este un ciclu impar, așa că nu este bipartit și are nevoie de 3 culori. Oricare două vârfuri sunt la cel mult 2 muchii distanță, deci diametrul este 2. Toate cele zece grade sunt impare, deci nu are drum eulerian, și nu poate fi desenat fără intersecții.
Drumuri euleriene și podurile din Königsberg
Orașul Königsberg avea șapte poduri care legau patru porțiuni de uscat, iar oamenii se întrebau dacă se poate face o plimbare trecând peste fiecare pod exact o dată. În 1736, Leonhard Euler a arătat că nu se poate, și așa a luat naștere teoria grafurilor. De fiecare dată când o plimbare trece printr-o porțiune de uscat, folosește două poduri, deci doar punctul de plecare și cel de sosire pot avea un număr impar de poduri, iar toate cele patru porțiuni din Königsberg aveau un număr impar. Un traseu care folosește fiecare muchie o singură dată se numește astăzi drum eulerian sau, dacă se termină unde a început, ciclu eulerian. Carl Hierholzer a demonstrat în 1873 că această condiție este și suficientă: dacă toate muchiile se află într-o singură componentă și cel mult două grade sunt impare, traseul există, iar metoda lui, care îmbină trasee închise, îl găsește și astăzi.
Distanța, diametrul și complementarul
Distanța dintre două vârfuri este cel mai mic număr de muchii de pe un drum care le unește, iar diametrul este cea mai mare distanță din graf; într-un graf neconex, diametrul este infinit. Rețelele sociale au diametre mici, ideea din spatele celor „șase grade de separare”. Complementarul unui graf are aceleași vârfuri și unește exact perechile care nu erau unite. Dintre un graf și complementarul său, cel puțin unul este întotdeauna conex.
Explorați
Laboratorul se deschide cu graful Petersen colorat în trei culori. Faceți clic pe Grade și verificați lema strângerilor de mână, faceți clic pe Bipartit pentru a vedea un ciclu impar, apoi încărcați cubul și urmăriți cum apar cele două părți. Încărcați căsuța și faceți clic pe Drum eulerian pentru a vedea de unde trebuie să înceapă linia. Desenați propriul graf și adăugați muchiile una câte una: urmăriți cum se scurtează cel mai scurt ciclu, cum scade diametrul și cum crește numărul cromatic când este adăugată ultima muchie a unui K4.
Întrebări frecvente
Care este diferența dintre un drum, un traseu și un parcurs?
Un parcurs este orice succesiune de vârfuri unite prin muchii și poate repeta atât vârfuri, cât și muchii. Un traseu poate repeta vârfuri, dar nu și muchii; de aceea un drum eulerian, care este de fapt un traseu, poate trece de mai multe ori prin același vârf. Un drum nu repetă nici vârfuri, nici muchii.
Ce este teorema celor patru culori?
Ea afirmă că orice graf care poate fi desenat pe hârtie fără ca muchiile să se intersecteze poate fi colorat cu cel mult patru culori, așa că nicio hartă nu are nevoie de mai mult de patru. A fost demonstrată în 1976 de Kenneth Appel și Wolfgang Haken cu ajutorul unui calculator, fiind prima teoremă importantă demonstrată astfel.
Ce este un ciclu hamiltonian?
Un ciclu care trece exact o dată prin fiecare vârf, în loc de fiecare muchie. Seamănă cu problema lui Euler, dar nu se cunoaște niciun test simplu pentru el: a decide dacă un graf are un astfel de ciclu este o problemă NP-completă. Graful Petersen are un drum hamiltonian, dar nu are niciun ciclu hamiltonian.
Unde se folosește teoria grafurilor?
Planificatoarele de rute caută în grafuri rutiere, motoarele de căutare ordonează paginile web după legăturile dintre ele, compilatoarele colorează grafuri pentru a împărți registrele procesorului, orarele evită suprapunerile colorând un graf al conflictelor, chimiștii numără molecule reprezentate ca grafuri, iar rețelele de calculatoare, liniile electrice și rețelele de prieteni sunt studiate ca grafuri.
Ești gata să încerci?
Deschide PictorX în browser – fără instalare și fără card de credit.
Deschideți laboratorul de teoria grafurilor