Grafuri neorientate: noțiuni

Vârfuri, muchii, grade, lanțuri și cicluri: vocabularul fără de care nu poți citi enunțurile.

Ce este un graf

Un graf neorientat este format dintr-o mulțime de vârfuri (noduri) și o mulțime de muchii. Fiecare muchie leagă două vârfuri.

Aceasta e toată definiția. Restul lecției dă nume unor situații care apar des.

Grafurile modelează orice relație simetrică: orașe legate prin șosele, oameni care se cunosc între ei, camere legate prin uși. „Neorientat" înseamnă că relația merge în ambele sensuri: dacă A este legat de B, atunci și B este legat de A.

De obicei n este numărul de vârfuri, iar m numărul de muchii. Vârfurile se numerotează de la 1 la n.

Vocabularul

Muchie: o pereche de vârfuri, scrisă [x, y] sau (x, y). Într-un graf neorientat, [x, y] și [y, x] sunt aceeași muchie.

Vârfuri adiacente (vecine): unite printr-o muchie.

Muchie incidentă cu un vârf: are acel vârf ca extremitate.

Gradul unui vârf: câte muchii sunt incidente cu el, adică câți vecini are. Se notează grad(x).

Vârf izolat: are gradul 0.

Vârf terminal: are gradul 1.

Prima teoremă

Suma gradelor tuturor vârfurilor este dublul numărului de muchii:

grad(1) + grad(2) + … + grad(n) = 2 · m

Motivul e simplu: fiecare muchie are două capete, deci contribuie cu 1 la gradul fiecăruia dintre ele.

Consecințe folosite des la Subiectul I:

• Suma gradelor este întotdeauna pară.
• Numărul de vârfuri de grad impar este par.
• Dacă știi suma gradelor, știi numărul de muchii: m = suma / 2.

Lanțuri și cicluri

Lanț: o succesiune de vârfuri în care oricare două consecutive sunt unite printr-o muchie. Lungimea unui lanț este numărul de muchii, nu de vârfuri. Un lanț cu 4 vârfuri are lungimea 3.

Lanț elementar: nu repetă niciun vârf.

Ciclu: un lanț care se întoarce în vârful de plecare, fără să repete muchii. Un ciclu elementar nu repetă vârfuri (în afară de primul, care este și ultimul).

Cel mai scurt ciclu într-un graf neorientat are lungimea 3 (un triunghi). (Lungimea 2 ar însemna aceeași muchie parcursă de două ori, ceea ce nu e permis.)

Conexitate

Un graf este conex dacă între oricare două vârfuri există un lanț, adică din orice vârf poți ajunge în oricare altul.

Dacă nu este conex, se descompune în componente conexe: bucăți în care se poate circula, dar între care nu există nicio muchie.

Cea mai frecventă cerință de la grafuri este „câte componente conexe are graful". Se rezolvă cu o parcurgere, cum vom vedea.

Grafuri speciale

Graf complet cu n vârfuri: există muchie între oricare două vârfuri distincte. Are

m = n(n-1)/2

muchii, iar fiecare vârf are gradul n-1. Formula se deduce ușor: fiecare dintre cele n vârfuri este legat de celelalte n-1, iar fiecare muchie a fost numărată de două ori.

Este și numărul maxim de muchii pe care le poate avea un graf cu n vârfuri.

Graf nul: nu are muchii, deci toate vârfurile sunt izolate.

Graf bipartit: vârfurile se pot împărți în două grupuri astfel încât fiecare muchie să lege un vârf dintr-un grup cu unul din celălalt.

Subgraf: se obține ștergând vârfuri (și toate muchiile incidente cu ele).

Graf parțial: se obține ștergând doar muchii. Vârfurile rămân toate.

La examen ți se cere explicit diferența dintre subgraf și graf parțial, iar cele două se confundă des. Ține minte: parțial = păstrez toate vârfurile.

Câteva calcule care apar des

Numărul minim de muchii ca un graf cu n vârfuri să fie conex: n - 1. Un graf conex cu exact n-1 muchii este un arbore.

Numărul maxim de muchii ca un graf cu n vârfuri să fie neconex: izolezi un vârf și faci complet restul grafului, deci (n-1)(n-2)/2. Cu o muchie mai mult, graful este obligatoriu conex.

Numărul de grafuri neorientate distincte cu n vârfuri: fiecare dintre cele n(n-1)/2 muchii posibile poate exista sau nu, deci 2^(n(n-1)/2).

Aceste trei rezultate acoperă majoritatea itemilor de teorie de la Subiectul I.

Un exemplu de raționament

> Un graf neorientat cu 8 vârfuri are 6 vârfuri de grad 3 și 2 vârfuri de grad 4. Câte muchii are?

Suma gradelor este 6·3 + 2·4 = 26. Deci m = 26 / 2 = 13.

> Poate un graf cu 5 vârfuri să aibă toate vârfurile de grad 3?

Suma ar fi 15, un număr impar. Asta e imposibil, pentru că suma gradelor este mereu pară, deci răspunsul este nu.

De reținut

• Suma gradelor = 2m. De aici ies aproape toate întrebările de numărare.
• Numărul de vârfuri de grad impar este par.
• Lungimea unui lanț se numără în muchii.
• Conex = din orice vârf ajungi oriunde. Altfel graful are mai multe componente conexe.
• Complet: n(n-1)/2 muchii, grad n-1.
• Graf parțial = păstrez toate vârfurile. Subgraf = șterg și vârfuri.