Graf regulat

Graf al unui cub

Graf al unui octaedru

În teoria grafurilor, un graf regulat este un graf unde fiecare nod are același număr de vecini; adică fiecare nod are același grad sau valență. Un graf orientat regulat trebuie să îndeplinească și condiția ca gradele interioare și exterioare ale nodurilor interne să fie egale între ele.^[1] Un graf regulat cu noduri de grad k se numește graf k-regulat sau graf regulat de grad k. De asemenea, din lema strângerii mâinilor^⁠(d), un graf regulat conține un număr par de noduri de grad impar.

Grafurile regulate de grad cel mult 2 sunt ușor de clasificat: un graf 0-regulat este format din noduri deconectate, un graf 1-regulat este format din muchii deconectate și un graf 2-regulat constă dintr-o reuniune disjunctă de cicluri și lanțuri infinite.

Un graf 3-regulat este cunoscut drept graf cubic^⁠(d).

• 
  graf 0-regulat
• 
  graf 1-regulat
• 
  graf 2-regulat
• 
  graf 3-regulat

Un graf regulat tare este un graf regulat în care fiecare pereche de noduri adiacentă are același număr l de vecini în comun și fiecare pereche de noduri neadiacente are același număr n de vecini în comun. Cele mai mici grafuri care sunt regulate, dar nu regulate tari, sunt graful ciclu și graful circulant cu 6 noduri.

Graful complet K_m este regulat tare pentru orice m.

O teoremă a lui Crispin Nash-Williams afirmă că orice graf k-regulat pe 2k + 1 noduri are un drum hamiltonian.

Este bine cunoscut faptul că condițiile necesare și suficiente pentru ca un graf ${\displaystyle k}$-regulat de ordinul ${\displaystyle n}$ să existe sunt ca ${\displaystyle n\geq k+1}$ și că ${\displaystyle nk}$ să fie par.

Demonstrație: După cum se știe, un graf complet are fiecare pereche de noduri distincte conectate între ele printr-o muchie unică. Deci în graful complet numărul de muchii este maxim, ${\displaystyle {\binom {n}{2}}={\dfrac {n(n-1)}{2}},}$ iar gradul este ${\displaystyle n-1}$. Deci ${\displaystyle k=n-1,n=k+1}$. Acesta este ${\displaystyle n}$ minim pentru un anumit ${\displaystyle k}$. De reținut și că dacă orice graf regulat are ordinul ${\displaystyle n}$, atunci numărul de muchii este ${\displaystyle {\dfrac {nk}{2}},}$ deci ${\displaystyle nk}$ trebuie să fie par. În acest caz, este ușor de construit grafuri regulate, luând în considerare parametrii corespunzători pentru grafurile circulante.

Fie A matricea de adiacență a unui graf. Atunci graful este regulat dacă și numai dacă ${\displaystyle {\textbf {j}}=(1,\dots ,1)}$ este o valoare proprie a lui A.^[2] Valoarea proprie va fi gradul constant al grafului. Vectorii proprii corespunzători altor valori proprii sunt ortogonali cu ${\displaystyle {\textbf {j}}}$, deci pentru astfel de vectori proprii ${\displaystyle v=(v_{1},\dots ,v_{n}),}$ ${\displaystyle \sum _{i=1}^{n}v_{i}=0}$.

Un graf regulat de gradul k este conex dacă și numai dacă valoarea proprie k are multiplicitatea unu. Condiția „numai dacă” este o consecință a teoremei Perron–Frobenius^⁠(d).^[2]

Fie G un graf k-regulat cu diametrul D și valorile proprii ale matricei de adiacență ${\displaystyle k=\lambda _{0}>\lambda _{1}\geq \cdots \geq \lambda _{n-1}}$. Dacă G nu este bipartit, atunci^[3]

${\displaystyle D\leq {\frac {\log {(n-1)}}{\log(\lambda _{0}/\lambda _{1})}}+1.}$

Există algoritmi rapizi pentru a enumera, până la izomorfism, toate grafurile regulate cu un grad și un număr dat de noduri.^[4]

• en Nash-Williams, Crispin (1969), Valency Sequences which force graphs to have Hamiltonian Circuits, University of Waterloo Research Report, Waterloo, Ontario: University of Waterloo 

• Materiale media legate de graf regulat la Wikimedia Commons
• en Eric W. Weisstein, Regular Graph la MathWorld.
• en Eric W. Weisstein, Strongly Regular Graph la MathWorld.
• en GenReg software and data by Markus Meringer.

Portal Matematică