Graf regulat

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

Graf al unui cub

Graf al unui octaedru

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 $2 k + 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.^[2] 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).^[2]

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^[3]

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.^[4]

Note

^ en Chen, Wai-Kai (1997). Graph Theory and its Engineering Applications . World Scientific. pp. 29. ISBN 978-981-02-1859-1.
^ ^a ^b en Cvetković, D. M.; Doob, M.; and Sachs, H. Spectra of Graphs: Theory and Applications, 3rd rev. enl. ed. New York: Wiley, 1998.
^ en Gregory Quenell, Spectral diameter estimates for k-regular graphs, Advances in Mathematics, 106(1):122–148, 1994
^ en Meringer, Markus (1999). „Fast generation of regular graphs and construction of cages” (PDF). Journal of Graph Theory. 30 (2): 137–146. doi:10.1002/(SICI)1097-0118(199902)30:2<137::AID-JGT7>3.0.CO;2-G.

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.

Portal Matematică

[1] Chen, Wai-Kai (1997). Graph Theory and its Engineering Applications . World Scientific. pp. 29. ISBN 978-981-02-1859-1.

[Cvetkovic-2] Cvetković, D. M.; Doob, M.; and Sachs, H. Spectra of Graphs: Theory and Applications, 3rd rev. enl. ed. New York: Wiley, 1998.

[3] Gregory Quenell, Spectral diameter estimates for k-regular graphs, Advances in Mathematics, 106(1):122–148, 1994

[4] Meringer, Markus (1999). „Fast generation of regular graphs and construction of cages” (PDF). Journal of Graph Theory. 30 (2): 137–146. doi:10.1002/(SICI)1097-0118(199902)30:2<137::AID-JGT7>3.0.CO;2-G.

[1]

[2]

[3]

[4]