Grafuri conexe și arbori

Un graf neorientat este conex dacă între oricare două vârfuri există un lanț. Un arbore este un graf conex fără cicluri. Pentru un arbore cu $n$ vârfuri, numărul muchiilor este $n-1$.

Exemplu rezolvat. Luăm vârfurile $A,B,C,D$ și muchiile $AB,BC,CD$.

1. De la orice vârf putem ajunge la oricare altul, deci graful este conex.
2. Nu există ciclu.
3. Are $4$ vârfuri și $3=4-1$ muchii; este arbore.

Un lanț este o succesiune de vârfuri în care oricare două vârfuri consecutive sunt legate printr-o muchie. Un ciclu este un lanț închis cu cel puțin trei muchii, fără repetarea vârfurilor în afara primului și ultimului.

Într-un arbore există exact un lanț elementar între două vârfuri distincte. Eliminarea unei muchii îl deconectează, iar adăugarea unei muchii între vârfuri deja existente creează un ciclu. Un arbore parțial al unui graf conex conține toate vârfurile și doar muchii ale grafului inițial.

Exemplu rezolvat. Graful cu vârfurile $\{1;2;3;4\}$ și muchiile $[1,2]$, $[2,3]$, $[3,4]$, $[4,1]$, $[1,3]$ este conex, dar are cicluri. Alegem muchiile $[1,2]$, $[2,3]$, $[3,4]$: acestea păstrează toate cele patru vârfuri, formează un lanț între oricare două și nu închid niciun ciclu. Cele trei muchii formează un arbore parțial. Muchia $[4,1]$ nu poate fi adăugată fără a crea un ciclu.

Un graf care nu este conex se descompune în componente conexe: mulțimi maximale de vârfuri între care există lanțuri. Un graf cu $n$ vârfuri, $M$ muchii și $c$ componente conexe satisface $M\ge n-c$, cu egalitate dacă și numai dacă este fără cicluri (o pădure). Arborii sunt cele mai economice grafuri conexe: conectează toate vârfurile cu cele mai puține muchii, de aceea modelează rețele de cabluri sau de conducte care trebuie să lege toate punctele fără redundanță. Într-un arbore, eliminarea oricărei muchii îl împarte în exact două componente conexe, iar adăugarea unei muchii noi între vârfuri deja existente creează exact un ciclu. Un arbore cu $n\ge 2$ vârfuri are cel puțin două vârfuri de grad $1$, numite frunze, și suma gradelor egală cu $2(n-1)$. Un graf conex cu $n$ vârfuri și $M$ muchii are un arbore parțial prin eliminarea a $M-n+1$ muchii alese astfel încât graful rămas să rămână conex; acest număr se numește numărul ciclomatic și este zero doar pentru arbori. Pentru ciclul cu $4$ vârfuri, $M=4$, deci $4-4+1=1$ muchie se elimină, iar arborii parțiali sunt $4$ (după muchia aleasă).

Exemplu rezolvat. Un arbore are $8$ vârfuri; $5$ dintre ele sunt frunze, iar celelalte trei au același grad $k$. Află $k$.

1. Numărul muchiilor este $8-1=7$, deci suma gradelor este $14$.
2. Frunzele contribuie cu $5\cdot 1=5$, iar celelalte trei cu $3k$.
3. Din $5+3k=14$ rezultă $k=3$.

Verificare: gradele $1,1,1,1,1,3,3,3$ au suma $14$.

Exemplu rezolvat. Un graf conex are $6$ vârfuri și $9$ muchii. Câte muchii trebuie eliminate pentru a obține un arbore parțial și cum arată rezultatul?

1. Un arbore parțial are $6-1=5$ muchii.
2. Trebuie eliminate $9-5=4$ muchii, adică numărul ciclomatic $9-6+1=4$.
3. La fiecare eliminare se alege o muchie dintr-un ciclu, pentru ca graful să rămână conex.

Rezultatul conține toate cele $6$ vârfuri, este conex și nu are cicluri.

Greșeli frecvente

• Greșit: un arbore poate avea o singură frunză.
  Corect: orice arbore cu cel puțin două vârfuri are cel puțin două frunze.
• Greșit: orice graf cu $n-1$ muchii este arbore.
  Corect: trebuie și conexitate.
• Greșit: un arbore poate avea un ciclu.
  Corect: este aciclic.
• Greșit: un arbore parțial poate omite vârfuri.
  Corect: păstrează toate vârfurile.

Înainte și după