Introducere în teoria grafurilor – Noțiuni elementare despre grafuri

Introducere în teoria grafurilor – Noțiuni elementare despre grafuri

Matematic, un graf este o pereche ordonată de mulțimi, G=(V,E)G = (V, E) unde VV reprezintă o mulțime finită și nevidă de elemente numite vârfuri (sau noduri), iar EE este o mulțime de perechi cu elemente din VV numite muchii (dacă sunt neordonate) sau arce (dacă sunt ordonate). În primul caz graful se numește neorientat, iar în al doilea orientat (sau digraf).

Exemple de grafuri din viața de zi cu zi

Practic, un graf este un mod de a reprezenta elementele unei mulțimi și conexiunile dintre acestea, stabilite pe baza unei anumite relații. Graful este neorientat dacă relația respectivă este reflexivă, sau orientat în caz contrar. Iată câteva exemple:

1. Harta unui oraș

Nodurile sunt intersecții, iar o muchie dintre două noduri reprezintă faptul că există o stradă între cele două intersecții. În cazul în care vrem să evidențiem faptul că unele străzi au sens unic, graful devine orientat. Astfel, dacă există muchie de la AA la BB înseamnă că din AA se poate ajunge în BB prin acel drum, dar nu și reciproc.

Graf cu județe

2. O rețea de socializare

Nodurile sunt utilizatorii, iar o muchie reprezintă relația de prietenie între doi utilizatori. Cum prietenia este o relație reflexivă, dacă AA este prieten cu BB înseamnă că și BB este prieten cu AA Așadar, vorbim despre un graf neorientat.

Graf cu o rețea de socializare

3. Un circuit electric

Făcând abstracție de elementele de circuit de pe laturile schemei (cum ar fi rezistorii), aceasta este un graf în care vârfurile sunt nodurile rețelei, iar ciclurile elementare sunt ochiurile acesteia. Fizicianul Kirchhoff a studiat rețelele electrice folosind metode care aparțin astăzi teoriei grafurilor, contribuind la dezvoltarea acesteia.

Graf obținut dintr-un circuit electric

4. Formula de structură a unei substanțe chimice

Nodurile vor fi atomii (sau grupările de atomi), iar muchiile legăturile dintre aceștia. Eventual, costul fiecărei muchii poate reține tipul legăturii chimice dintre extremitățile ei.

Graf pentru propenă

5. Un joc de cuvinte

Acesta e un exemplu mult mai abstract și interesant, găsit pe CSAcademy. Să presupunem că pornim de la un cuvânt de trei litere, căruia îi putem schimba succesiv câte o literă astfel încât să obținem un nou cuvânt valid. Scopul este de a ajunge la un cuvânt dat printr-un număr minim de pași. De exemplu (nu prea am găsit cuvinte în română):

dogbogbotbat\texttt{dog} \to \texttt{bog} \to \texttt{bot} \to \texttt{bat}

Putem modela un graf neorientat în care fiecare nod reține câte un cuvânt valid de trei litere. O muchie reprezintă faptul că se poate ajunge de la o extremitate la cealaltă printr-un singur pas. Pentru a rezolva problema va mai trebui doar să determinăm drumul minim de la nodul cu primul cuvânt la cel cu al doilea.

Graf (joc de cuvinte)

Grafurile se regăsesc des în viața de zi cu zi. De aceea, este important studiul algoritmilor specifici acestora, cum ar fi cei de găsire a drumului de lungime minimă (între două localități să zicem) și cel de determinare a fluxului maxim de cost minim (într-o rețea de țevi).

Noțiuni elementare din teoria grafurilor

Cele două noduri xx și yy ce formează muchia [x,y][x, y] se numesc extremități. În cazul grafurilor orientate, pentru arcul (x,y)(x, y) xx se numește extremitate inițială, iar yy extremitate finală. În plus, vom spune că xx și yy sunt noduri adiacente, și incidente la muchia/ arcul pe care îl formează.

Exemplu de extremități

Într-un graf neorientat, nodurile cu gradul 00 se numesc noduri izolate, iar cele cu gradul 11 se numesc noduri terminale.

Graf simplu, multigraf

Între oricare două noduri ale unui graf simplu poate exista cel mult o muchie/ arc. În caz contrar, structura de date se va numi multigraf. Într-un multigraf, muchiile cu aceeași pereche de extremități se numesc muchii paralele. În plus, muchiile cu extremități identice (de la un nod la el însuși), se numesc bucle.

Aici apare o discuție, deoarece unii autori de specialitate consideră că doar multigrafurile (nu și grafurile) pot avea bucle, pe când ceilalți susțin contrariul. Preferabilă este prima variantă, pentru că altfel multe formule clasice legate de grafuri s-ar complica. De obicei se specifică în enunțul problemelor dacă graful poate avea bucle sau nu. Oricum, noi vom lucra doar cu grafuri simple.

Exemplu de multigraf

Numărul maxim de muchii/ arce

Numărul maxim de muchii ale unui graf neorientat cu nn noduri este n(n1)/2n(n-1)/2 pentru că, având la dispoziție nn noduri, se pot forma Cn2=n(n1)/2C^2_n = n(n - 1) / 2 perechi neordonate, iar în cel mai fericit caz, pentru oricare două noduri xx și yy din VV există muchia [x,y][x, y] Similar, numărul maxim de arce ale unui graf orientat cu nn noduri este 2Cn2=n(n1)2C^2_n = n(n - 1) pentru că două noduri xx și yy pot contribui cu maxim două arce: (x,y)(x, y) și (y,x)(y, x)

Numărul de grafuri orientate/ neorientate

De aici mai putem deduce două formule: Numărul de grafuri neorientate cu nn noduri este 2n(n1)/22^{n(n - 1) / 2} pentru că între fiecare două noduri pot exista 00 sau 11 muchii. Analog, numărul de grafuri orientate cu nn noduri este 4n(n1)/24^{n(n - 1) / 2} pentru că între fiecare două noduri xx și yy pot exista arcul (x,y)(x, y) arcul (y,x)(y, x) ambele sau niciunul.

Gradul unui nod

Într-un graf neorientat, gradul unui nod reprezintă numărul de muchii incidente cu acesta, și se notează cu d(x)d(x) Într-un graf orientat, gradul interior al nodului xx se notează cu d(x)d^{-}(x) și este egal cu numărul de arce cu extremitatea finală xx iar gradul exterior, notat cu d+(x)d^{+}(x) este numărul arcelor cu extremitatea inițială xx

Exemple de grade

Suma gradelor nodurilor unui graf neorientat este egală cu dublul numărului său de muchii, pentru că fiecare muchie contribuie cu câte o unitate la gradul a două noduri:

xVd(x)=2E\sum_{x \in V} d(x) = 2|E|

Atât suma gradelor interioare cât și suma gradelor exterioare ale nodurilor unui graf orientat sunt egale cu numărul de arce ale grafului, pentru că fiecare muchie contribuie cu câte o unitate la fiecare sumă:

xVd(x)=xVd+(x)=E\sum_{x \in V} d^{-}(x) = \sum_{x \in V} d^{+}(x) = |E|

Grafuri asociate unui graf

Fie graful G=(V,E)G = (V, E) Graful G=(V,E)G' = (V, E') cu EEE' \subseteq E este un graf parțial al grafului GG Se observă că acesta se poate obține prin eliminarea unor muchii/ arce din graful inițial. Numărul grafurilor parțiale ale lui GG este 2E2^{|E|} (pentru fiecare muchie avem două variante: o ștergem sau nu).

Graful G=(V,E)G^{\prime\prime} = (V^{\prime\prime}, E^{\prime\prime}) cu VVV^{\prime\prime} \subseteq V și EE^{\prime\prime} mulțimea tuturor muchiilor/ arcelor din EE cu ambele extremități în VV^{\prime\prime} se numește subgraf al lui GG Acesta poate fi obținut eliminând unele noduri din GG împreună cu toate muchiile incidente la acestea. Numărul de subgrafuri ale lui GG este 2V12^{|V|} - 1 (numărul submulțimilor lui VV excluzând mulțimea vidă, deoarece graful nu poate avea 00 noduri).

Un subgraf parțial este, după cum îi spune și numele, un subgraf din care s-au eliminat niște muchii.

Graf parțial, subgraf, subgraf parțial

Graful complementar unui graf neorientat GG are aceeași mulțime de vârfuri, dar mulțimea muchiilor conține doar muchiile care nu apar în GG

Exemplu graf complementar

Pentru un graf orientat GG graful GT=(V,ET)G^T = (V, E^T) se numește graful transpus al lui GG dacă ET={(y,x)(x,y)E}E^T = \{(y, x) \mid (x, y) \in E\}

Exemplu graf transpus

Tipuri speciale de grafuri

Un graf se numește complet dacă oricare două noduri ale sale sunt adiacente. Graful neorientat complet cu nn noduri se notează KnK_n și conține n(n1)/2n(n - 1) / 2 muchii.

Există un singur graf neorientat complet cu nn noduri, însă grafurile orientate complete cu nn noduri sunt mai multe. Mai exact, între oricare două noduri xx și yy pot exista ori arcul (x,y)(x, y) ori (y,x)(y, x) ori ambele. Deci, numărul grafurilor orientate complete cu nn noduri este 3n(n1)/23^{n(n - 1) / 2}

Grafuri complete

Un graf orientat se numește antisimetric în cazul în care pentru oricare două noduri xx și yy dacă există arcul (x,y)(x, y) atunci nu există și arcul (y,x)(y, x) Cu alte cuvinte, între două noduri există cel mult un arc. Există 3n(n1)/23^{n(n - 1) / 2} grafuri antisimetrice, deoarece între două noduri xx și yy pot exista arcul (x,y)(x, y) arcul (y,x)(y, x) sau niciunul.

Un graf orientat complet și antisimetric se numește graf turneu. Numărul de grafuri turneu cu nn noduri este 2n(n1)/22^{n(n - 1) / 2} căci între două noduri xx și yy poate exista arcul (x,y)(x, y) sau arcul (y,x)(y, x)

Graf antisimetric, graf turneu

Un graf neorientat se numește bipartit dacă mulțimea muchiilor sale poate fi partiționată în două submulțimi AA și BB astfel încât orice muchie are o extremitate în AA și una în BB Un graf bipartit complet este un graf bipartit în care fiecare nod din AA este adiacent cu fiecare nod din BB

Graf bipartit, graf bipartit complet

Un graf neorientat se numește regulat dacă toate nodurile sale au același grad.

Grafuri regulate

Un graf stea (star graph) este un graf neorientat format dintr-un nod la care s-au unit mai multe noduri terminale. Graful stea cu nn noduri terminale se notează cu SnS_n De exemplu, așa arată S5S_5

Graf stea

Lanț, ciclu, drum, circuit

Într-un graf neorientat, un lanț este o secvență de noduri [x1,x2,,xk][x_1, x_2, \ldots, x_k] cu proprietatea că oricare două noduri consecutive din secvență sunt adiacente. Extremitatea inițială a lanțului este x1x_1 iar cea finală xkx_k Lungimea unui lanț este numărul muchiilor din care este compus, deci k1k - 1

Un lanț este elementar dacă nu conține de mai multe ori același nod. Un lanț se numește simplu dacă nu conține de mai multe ori aceeași muchie. Se observă că orice lanț elementar este automat și simplu. Un ciclu este un lanț simplu pentru care extremitatea inițială este aceeași cu cea finală. Ciclul este elementar dacă nu conține de mai multe ori același nod (cu excepția extremităților).

Exemple de lanțuri și cicluri

Similar sunt definite și drumurile (pentru grafurile orientate): Un drum este o secvență de noduri (x1,x2,,xk)(x_1, x_2, \ldots, x_k) cu proprietatea că pentru oricare două noduri consecutive xix_i și xi+1x_{i+1} există arcul (xi,xi+1)(x_i, x_{i+1}) În plus, ciclul se va numi de fapt circuit.

Exemple de drumuri și circuite

Un lanț/ drum/ ciclu/ circuit se numește hamiltonian dacă trece prin fiecare nod al grafului exact o singură dată. Un lanț/ drum/ ciclu/ circuit se numește eulerian dacă trece prin fiecare dintre muchiile/ arcele grafului exact o singură dată.

Lanț hamiltonian, ciclu eulerian

Numărul ciclurilor hamiltoniene dintr-un graf neorientat complet

Numărul de cicluri hamiltoniene din KnK_n este egal cu (n1)!/2(n-1)!/2 Cum ajungem la acest rezultat? Mai întâi fixăm primul nod al ciclului în 11 căci vorbind de un ciclu, nu contează de unde începem. De exemplu, ciclul [1,2,4,3,1][1, 2, 4, 3, 1] este tot una cu [3,1,2,4,3][3, 1, 2, 4, 3] Rămân de permutat restul de n1n - 1 noduri ale grafului, de unde rezultă acel (n1)!(n - 1)! La final, împărțim rezultatul la 22 pentru a nu număra același ciclu de două ori: o dată scris de la stânga la dreapta și o dată de la dreapta la stânga.

Ciclurile hamiltoniene ale K4

Conexitate

Un graf neorientat GG se numește conex dacă există lanț între oricare două noduri ale sale. O componentă conexă a lui GG este un subgraf conex maximal al său.

Exemplu componente conexe

Un graf orientat GG se numește tare-conex dacă pentru oricare două noduri xx și yy ale sale există atât drum de la xx la yy cât și drum de la yy la xx O componentă tare-conexă a lui GG este un subgraf tare-conex maximal al său.

Grafuri ponderate

Adesea, modelarea problemelor practice necesită utilizarea unor grafuri în care muchiilor/ arcelor li se asociază costuri (ponderi). Astfel de grafuri se numesc grafuri ponderate. Funcția care asociază câte un cost fiecărei muchii/ arc a grafului se numește funcție de cost. De exemplu, avem un graf G=(V,E)G = (V, E) ce reprezintă harta unei țări, și funcția f:VNf : V \to \mathbb{N}^{*} unde f([x,y])f([x, y]) reprezintă lungimea străzii dintre orașele xx și yy

Exemplu de graf ponderat

Note

  • Mulțimea vârfurilor unui graf poate conține orice fel de elemente, dar pentru simplitate am ales V={1,2,,V}V = \{1, 2, \ldots, |V|\}

  • O partiție a unei mulțimi reprezintă un set de submulțimi ale sale, nevide și disjuncte, pentru care reuniunea lor este egală cu mulțimea respectivă.

  • Perechile neordonate se notează folosind paranteze pătrate, pe când perechile ordonate se notează folosind paranteze rotunde. Din acest motiv, muchiile și lanțurile se notează folosind paranteze pătrate, în timp ce arcele și drumurile se notează folosind paranteze rotunde. Din acest punct de vedere, diferența dintre lanțuri și drumuri este că un lanț este același atât citit de la stânga la dreapta, cât și de la dreapta la stânga.

  • Reprezentarea grafică a unui graf este alcătuită din niște cerculețe etichetate (nodurile), unite prin segmente (muchiile/arcele). Segmentele sunt orientate dacă graful este orientat, adică pe ele se pune o săgeată care indică sensul arcului. Dacă între două noduri există ambele arce, se desenează două linii curbate cu săgeată, sau un singur segment, cu săgeată la ambele capete.

    Exemplu de arce
  • Prin subgraf cu proprietatea PP maximal înțelegem că dacă am mai adăuga la el un nod, împreună cu muchiile incidente la acesta, proprietatea PP nu ar mai fi respectată.

  • Pentru demonstrația celor mai multe formule am folosit tehnica următoare: Asociez bijectiv grafului o funcție f:ABf : A \to B unde AA este mulțimea tuturor perechilor neordonate de noduri din VV iar BB mulțimea tuturor stărilor în care se poate afla o astfel de pereche. Numărul de grafuri va fi egal cu numărul de funcții ff care este dat de formula BA|B|^{|A|}

    Stările în care se pot afla două noduri dintr-un graf orientat

Acestea sunt noțiunile elementare din teoria grafurilor. Puteți citi în continuare despre reprezentarea grafurilor în C++. Dacă aveți vreo întrebare despre grafuri, o puteți adresa printr-un comentariu mai jos

Mulțumesc că ai citit acest articol.
Dacă vrei să susții blogul, poți cumpăra un abonament de 2$.

patreon

Lasă un comentariu!

0 comentarii