Grad (teoria grafurilor)
Unelte
General
Tipărire/exportare
Î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.[1] Gradul unui nod este notat cu
sau
.
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.
Formula sumei gradelor arată că, dat fiind un graf ,
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 unui graf neorientat este șirul necrescător al gradelor nodurilor acestuia;[2] 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.
|ISBN=
și |isbn=
(ajutor).|author-link=
și |authorlink=
(ajutor)|author-link=
și |authorlink=
(ajutor).|DOI=
și |doi=
(ajutor).