Graf regulat

Format:Imagine multiplă Î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 Format:Mvar se numește graf Format:Mvar-regulat sau graf regulat de grad Format:Mvar. De asemenea, din Format:Ill-wd, 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 Format:Ill-wd.

• 
  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 Format:Mvar de vecini în comun și fiecare pereche de noduri neadiacente are același număr Format:Mvar 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 Format:Mvar este regulat tare pentru orice Format:Mvar.

O teoremă a lui Crispin Nash-Williams afirmă că orice graf Format:Mvar-regulat pe Format:Math 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\ge 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, $(\genfrac{}{}{0ex}{}{n}{2})=\frac{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 $\frac{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ă $\mathbf{\text{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 $\mathbf{\text{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 Format:Ill-wd.

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

$D\le \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

• Format:En icon Format:Citation

Legături externe

• Format:Commonscat-inline
• Format:En icon Format:MathWorld
• Format:En icon Format:MathWorld
• Format:En icon GenReg software and data by Markus Meringer.