Grad (teoria grafurilor)

Un graf cu nodurile etichetate fiecare cu gradul lui

În teoria grafurilor, gradul (sau valența) unui nod dintr-un graf este numărul de muchii incidente^⁠(d) cu nodul, buclele^⁠(d) fiind numărate de două ori. Gradul unui nod $v$ este notat cu $\deg(v)$ sau $\deg v$.

Gradul maxim al unui graf G, notat cu Δ(G), și gradul minim al grafului, notat cu δ(G), sunt gradul maxim și, respectiv, minim al nodurilor sale. În graful din dreapta, gradul maxim este 5 și gradul minim este 0. Într-un graf regulat, toate gradele sunt la fel, și deci se poate vorbi de gradul grafului.

Lema strângerilor de mâini

Formula sumei gradelor arată că, dat fiind un graf $G=(V,E)$,

$\sum _{v\in V}\deg(v)=2|E|\,.$

Din formulă rezultă că, în orice graf, numărul de noduri cu grad impar este par. Această afirmație (precum și formula sumei gradelor) este cunoscută sub numele de lema strângerilor de mâini. Denumirea provine de la o problemă populară de matematică, care cerea să se demonstreze că în orice grup de oameni numărul de persoane care dau mâna cu un număr impar de alte persoane din grup este par.

Șirul gradelor

Două grafuri neizomorfe cu același șir de grade (3, 2, 2, 2, 2, 1, 1, 1).

Șirul gradelor unui graf neorientat este șirul necrescător al gradelor nodurilor acestuia; pentru graful de mai sus, este (5, 3, 3, 2, 2, 1, 0). Șirul gradelor este o invariantă a grafului^⁠(d), deci grafurile izomorfe^⁠(d) au același șir de grade. Cu toate acestea, șirul de grade nu identifică, în general, în mod unic un graf; în unele cazuri, grafuri neizomorfe pot avea același șir de grade.

Problema șirului gradelor este problema de a găsi unele sau toate grafurile cu un șir al gradelor dat ca un șir necrescător de numere întregi pozitive. (Zerourile de la urmă pot fi ignorate, deoarece acestea sunt ușor de realizat prin adăugarea unui număr adecvat de noduri izolate în graf.) Un șir care este șirul gradelor unui graf, adică pentru care problema șirului gradelor are o soluție, este numit grafic sau un șir grafic. Drept consecință a formulei sumei gradelor, orice șir cu sumă impară, cum ar fi (3, 3, 1), nu poate fi realizat ca șir al gradelor unui graf. Reciproca este și ea adevărată: dacă un șir are o sumă pară, atunci el este șirul gradelor unui multigraf. Construcția unui astfel de graf este simplă: se conectează nodurile cu grad impar în perechi printr-un cuplaj, și se completează restul de noduri cu grad par prin auto-bucle. Întrebarea dacă un anumit șir al gradelor poate fi realizat printr-un graf simplu este mai dificilă. Această problemă se numește și problema realizării grafului^⁠(d) și poate fi rezolvată prin teorema Erdős–Gallai^⁠(d) sau prin algoritmul Havel–Hakimi^⁠(d). Problema de a găsi sau de a estima numărul de grafuri cu un anumit șir al gradelor este o problemă din domeniul enumerării grafurilor.

Valori speciale

Un graf neorientat cu nodurile terminale 4, 5, 6, 7, 10, 11, și 12

• Un nod cu gradul 0 se numește nod izolat.
• Un nod cu gradul 1 se numește nod-frunză sau nod terminal. Această terminologie este comună cu studiul arborilor în teoria grafurilor și mai ales al arborilor^⁠(d) ca structuri de date.
• Un nod cu gradul n − 1 într-un graf cu n noduri se numește nod dominant^⁠(d).

Proprietăți globale

• Dacă toate nodurile unui graf au gradul k, graful se numește k-regulat și graful în sine se spune că are gradul k. Similar, un graf bipartit , în care fiecare două noduri aflate de aceeași parte a bipartiției au același grad se numește graf biregulat^⁠(d).
• Un graf conex neorientat are un drum eulerian dacă și numai dacă are 0 sau 2 noduri de grad impar. Daca are 0 noduri de grad impar, drumul eulerian este și „ciclu eulerian”.
• Un graf orientat este o pseudopădure^⁠(d) dacă și numai dacă fiecare nod are gradul exterior cel mult 1. Un graf funcțional este un caz special de pseudopădure în care fiecare nod are gradul exterior exact 1.
• Conform teoremei lui Brooks, orice graf, altul decât o clică sau un ciclu impar are număr cromatic cel mult Δ, și conform teoremei lui Vizing, orice graf are indicele cromatic cel mult Δ + 1.
• Un graf k-degenerat este un graf în care toate subgrafurile au un nod de grad cel mult k.

Bibliografie

• Diestel, Reinhard (2005), Graph Theory (în engleză) (ed. 3rd), Berlin, New York: Springer-Verlag, ISBN 978-3-540-26183-4  .
• Erdős, P.; Gallai, T. (1960), „Gráfok előírt fokszámú pontokkal” (PDF), Matematikai Lapok (în maghiară), 11: 264–274 .
• Havel, Václav (1955), „A remark on the existence of finite graphs”, Časopis pro pěstování matematiky (în cehă), 80: 477–480 
• Hakimi, S. L. (1962), „On realizability of a set of integers as degrees of the vertices of a linear graph. I”, Journal of the Society for Industrial and Applied Mathematics^⁠(d) (în engleză), 10: 496–506  .
• Sierksma, Gerard; Hoogeveen, Han (1991), „Seven criteria for integer sequences being graphic”, Journal of Graph Theory^⁠(d) (în engleză), 15 (2): 223–231, doi:10.1002/jgt.3190150209  .