Vizualizare sursă pentru „Grad (teoria grafurilor)”

[[Fișier:UndirectedDegrees_(Loop).svg|miniatura|Un graf cu nodurile etichetate fiecare cu gradul lui]]
În [[teoria grafurilor]], '''gradul''' (sau '''valența''') unui [[Nod (teoria grafurilor)|nod]] dintr-un [[graf]] este numărul de [[Glosar de teoria grafurilor|muchii]] {{Ill-wd|Q939272|3=incidente}} cu nodul, {{Ill-wd|Q512604|3=buclele}} fiind numărate de două ori.<ref>Diestel p.5</ref> Gradul unui nod <math>v</math> este notat cu <math>\deg(v)</math> sau <math>\deg v</math>. 

'''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 <math>G=(V, E)</math>,
:<math>\sum_{v \in V} \deg(v) = 2|E|\, .</math>

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 ==
[[Fișier:Conjugate-dessins.svg|miniatura|200x200px|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;<ref>Diestel p.278</ref> pentru graful de mai sus, este (5, 3, 3, 2, 2, 1, 0). Șirul gradelor este o {{Ill-wd|Q722659|3=invariantă a grafului}}, deci {{Ill-wd|Q303100|3=grafurile izomorfe}} 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|graf simplu]] este mai dificilă. Această problemă se numește și {{Ill-wd|Q18207520|3=problema realizării grafului}} și poate fi rezolvată prin {{Ill-wd|Q5385323|3=teorema Erdős–Gallai}} sau prin {{Ill-wd|Q18207665|3=algoritmul Havel–Hakimi}}. 
Problema de a găsi sau de a estima numărul de grafuri cu un anumit șir al gradelor este o problemă din domeniul [[Enumerarea grafurilor|enumerării grafurilor]].

== Valori speciale ==
[[Fișier:Depth-first-tree.png|miniatura|Un graf neorientat cu nodurile terminale 4, 5, 6, 7, 10, 11, și 12]]
* Un nod cu gradul 0 se numește [[Nod (teoria grafurilor)|nod izolat]].
* Un nod cu gradul 1 se numește nod-frunză sau nod terminal. Această terminologie este comună cu studiul [[Arbore (teoria grafurilor)|arborilor]] în teoria grafurilor și mai ales al {{Ill-wd|Q223655|3=arborilor}} ca [[Structură de date|structuri de date]].
* Un nod cu gradul ''n'' &#x2212; 1 într-un graf cu ''n'' noduri se numește {{Ill-wd|Q26789594|3=nod dominant}}.

== Proprietăți globale ==
* Dacă toate nodurile unui graf au gradul ''k,'' graful se numește [[Graf regulat|''k''-regulat]] și graful în sine se spune că are gradul ''k''. Similar, un [[Graf bipartit|graf bipartit]] , în care fiecare două noduri aflate de aceeași parte a bipartiției au același grad se numește {{Ill-wd|Q1153612|3=graf biregulat}}.
* 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 {{Ill-wd|Q7254793|3=pseudopădure}} 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''.

== Note ==
<references />

== Bibliografie ==
* {{Citation|title=Graph Theory|year=2005|last1=Diestel|first1=Reinhard|url=http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/|edition=3rd|location=Berlin, New York|publisher=Springer-Verlag|isbn=978-3-540-26183-4|ISBN=978-3-540-26183-4|language=engleză}}.
* {{Citation|title=Gráfok előírt fokszámú pontokkal|year=1960|last1=Erdős|last2=Gallai|first1=P.|first2=T.|author1-link=Paul Erdős|author2-link=Tibor Gallai|url=http://www.renyi.hu/~p_erdos/1961-05.pdf|journal=Matematikai Lapok|volume=11|pages=264&ndash;274|language=maghiară}}.
* {{Citation|title=A remark on the existence of finite graphs|year=1955|last=Havel|first=Václav|author-link=V. J. Havel|authorlink=V. J. Havel|url=http://eudml.org/doc/19050|journal=Časopis pro pěstování matematiky|volume=80|pages=477–480|language=cehă}}
* {{Citation|title=On realizability of a set of integers as degrees of the vertices of a linear graph. I|year=1962|last=Hakimi|first=S. L.|author-link=S. L. Hakimi|authorlink=S. L. Hakimi|journal=Journal of the {{Ill-wd|Q782100}}|volume=10|pages=496–506|language=engleză}}.
* {{Citation|title=Seven criteria for integer sequences being graphic|year=1991|last1=Sierksma|last2=Hoogeveen|first1=Gerard|first2=Han|journal={{Ill-wd|Q6295265}}|volume=15|issue=2|pages=223–231|doi=10.1002/jgt.3190150209|DOI=10.1002/jgt.3190150209|language=engleză}}.

[[Categorie:Teoria grafurilor]]