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. 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.

Existență

Este bine cunoscut faptul că condițiile necesare și suficiente pentru ca un graf $k$-regulat de ordinul $n$ să existe sunt ca $n\geq k+1$ și că $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, ${\binom {n}{2}}={\dfrac {n(n-1)}{2}},$ iar gradul este $n-1$. Deci $k=n-1,n=k+1$. Acesta este $n$ minim pentru un anumit $k$. De reținut și că dacă orice graf regulat are ordinul $n$, atunci numărul de muchii este ${\dfrac {nk}{2}},$ deci $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.

Proprietăți algebrice

Fie A matricea de adiacență a unui graf. Atunci graful este regulat dacă și numai dacă ${\textbf {j}}=(1,\dots ,1)$ este o valoare proprie a lui A. Valoarea proprie va fi gradul constant al grafului. Vectorii proprii corespunzători altor valori proprii sunt ortogonali cu ${\textbf {j}}$, deci pentru astfel de vectori proprii $v=(v_{1},\dots ,v_{n}),$ $\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).

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

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

Generare

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

Bibliografie

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

Legături externe

• 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.