Grafuri

Un graf este alcătuit din vârfuri și muchii care leagă perechi de vârfuri. El poate modela o rețea de drumuri, fără ca lungimea desenată a muchiilor să conteze. Gradul unui vârf este numărul muchiilor incidente, într-un graf simplu neorientat.

Exemplu rezolvat. Graful are vârfurile $A,B,C$ și muchiile $AB,BC,AC$.

1. Fiecare vârf este legat de celelalte două.
2. Gradul fiecărui vârf este $2$.
3. Suma gradelor este $6$, egală cu $2\cdot 3$ muchii.

Într-un graf neorientat, suma gradelor este de două ori numărul muchiilor, deoarece fiecare muchie contribuie la două grade. Un lanț, într-un graf neorientat, este o succesiune de vârfuri consecutive adiacente; într-un graf orientat, noțiunea corespunzătoare este drumul; un ciclu revine în vârful inițial fără repetări interioare. Precizează dacă graful este orientat, simplu ori ponderat înainte de a aplica o regulă.

Într-un graf orientat, legăturile sunt arce cu sens. Gradul interior al unui vârf numără arcele care intră, iar gradul exterior arcele care ies. Matricea de adiacență $A=(a_{ij})$ are $a_{ij}=1$ când există arcul $i\to j$; lista de adiacență enumeră pentru fiecare vârf vecinii spre care pleacă arce. Într-un graf neorientat, matricea de adiacență este simetrică.

Graful este un model matematic pentru relații: orașele și drumurile dintre ele, calculatoarele unei rețele și cablurile care le leagă, prietenii dintr-o clasă și relațiile lor. Desenul este doar o reprezentare; același graf se poate desena în mai multe feluri, iar lungimea sau forma muchiilor nu contează. Două reprezentări ale grafului sunt matricea de adiacență, în care elementul $a_{ij}$ este $1$ dacă vârfurile $i$ și $j$ sunt adiacente și $0$ în caz contrar, și lista de adiacență, care enumeră pentru fiecare vârf vecinii lui. Pentru un graf cu mult mai puține muchii decât perechi posibile de vârfuri, lista este mai economică, pe când matricea permite să afli imediat dacă două vârfuri sunt adiacente. Un graf neorientat simplu nu are bucle (muchii de la un vârf la el însuși) și nici muchii multiple; vârfurile legate printr-o muchie se numesc adiacente, iar un vârf cu gradul $0$ este izolat. Din formula $\sum \mathrm{deg}=2M$ rezultă că numărul vârfurilor de grad impar este par (lema strângerii de mână). La un graf orientat, suma gradelor interioare este egală cu suma gradelor exterioare și cu numărul arcelor.

Exemplu rezolvat. Graful neorientat cu vârfurile $A,B,C,D$ și muchiile $AB,BC,CD$ este reprezentat prin matricea de adiacență

Gradul unui vârf este suma liniei sale: $1,2,2,1$. Matricea este simetrică, iar suma tuturor elementelor este $6=2\cdot 3$, dublul numărului muchiilor.

Exemplu rezolvat. Există un graf simplu cu $4$ vârfuri și gradele $3,3,3,1$?

1. Suma gradelor este $10$, număr par, deci lema strângerii de mână nu exclude graful.
2. Un vârf de grad $3$ într-un graf cu $4$ vârfuri este adiacent cu toate celelalte trei.
3. Cele trei vârfuri de grad $3$ ar fi atunci adiacente cu al patrulea vârf, care ar avea gradul $3$, nu $1$.

Deci un astfel de graf nu există: condiția „suma gradelor pară” este necesară, dar nu suficientă.

Greșeli frecvente

• Greșit: un graf cu gradele $3,3,3,1$ există fiindcă suma gradelor este pară.
  Corect: suma pară este numai o condiție necesară; aici cele trei vârfuri de grad $3$ forțează gradul $3$ și pentru al patrulea vârf.
• Greșit: lungimea liniei desenate schimbă adiacența.
  Corect: contează numai ce vârfuri sunt legate.
• Greșit: suma gradelor este numărul muchiilor.
  Corect: este dublul lui, în graful neorientat.
• Greșit: orice succesiune de vârfuri este lanț într-un graf neorientat.
  Corect: vârfurile consecutive trebuie să fie adiacente.

Înainte și după