Vizualizare sursă pentru „Graf regulat”

{{Imagine multiplă
| direction = vertical
| width     = 200
| image1    = Cube graph.png
| caption1  = Graf al unui cub
| image2    = Octahedron graph.png
| caption2  = Graf al unui octaedru
}}
În [[teoria grafurilor]], un '''graf regulat''' este un [[graf]] unde fiecare [[nod (teoria grafurilor) |nod]] are același număr de vecini; adică fiecare nod are același [[grad (teoria grafurilor) |grad]] sau valență. Un [[graf orientat]] regulat trebuie să îndeplinească și condiția ca [[graf orientat#Grad_interior_și_grad_exterior |gradele interioare și exterioare ale nodurilor interne]] să fie egale între ele.<ref>{{en icon}} {{Cite book | last = Chen | first = Wai-Kai | title = Graph Theory and its Engineering Applications | publisher = World Scientific | year = 1997 | pages = [https://archive.org/details/graphtheoryitsen00chen/page/29 29] | isbn = 978-981-02-1859-1 | url-access = registration | url = https://archive.org/details/graphtheoryitsen00chen/page/29 }}</ref> Un graf regulat cu noduri de grad {{mvar|k}} se numește '''graf {{mvar|k}}-regulat''' sau graf regulat de grad {{mvar|k}}. De asemenea, din {{ill-wd| Q954454 |lema strângerii mâinilor}}, 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 grafuri |reuniune disjunctă]] de [[ciclu (teoria grafurilor) |cicluri]] și lanțuri infinite.

Un graf 3-regulat este cunoscut drept {{ill-wd| Q1374495||graf cubic}}.
<gallery>
Image:0-regular_graph.svg|graf 0-regulat
Image:1-regular_graph.svg|graf 1-regulat
Image:2-regular_graph.svg|graf 2-regulat
Image:3-regular_graph.svg|graf 3-regulat
</gallery>

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

[[Graf complet |Graful complet]] {{mvar|K{{sub|m}}}} este regulat tare pentru orice {{mvar|m}}.

O teoremă a lui Crispin Nash-Williams afirmă că orice graf {{mvar|k}}-regulat pe {{math|2''k'' + 1}} noduri are un [[drum hamiltonian]].

== Existență ==
Este bine cunoscut faptul că condițiile necesare și suficiente pentru ca un graf <math>k</math>-regulat de ordinul <math>n</math> să existe sunt ca <math> n \geq k+1 </math> și că <math>nk</math> 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, <math>\binom{n}{2} = \dfrac{n(n-1)}{2},</math> iar gradul este <math>n-1</math>. Deci <math>k=n-1,n=k+1</math>. Acesta este <math>n</math> minim pentru un anumit <math>k</math>. De reținut și că dacă orice graf regulat are ordinul <math>n</math>, atunci numărul de muchii este <math>\dfrac{nk}{2},</math> deci <math>nk</math> 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'' [[matrice de adiacență |matricea de adiacență]] a unui graf. Atunci graful este regulat [[dacă și numai dacă]] <math>\textbf{j}=(1, \dots ,1)</math> este o [[vectori și valori proprii |valoare proprie]] a lui ''A''.<ref name="Cvetkovic">{{en icon}} Cvetković, D. M.; Doob, M.; and Sachs, H. Spectra of Graphs: Theory and Applications, 3rd rev. enl. ed. New York: Wiley, 1998.</ref> Valoarea proprie va fi gradul constant al grafului. Vectorii proprii corespunzători altor valori proprii sunt ortogonali cu <math>\textbf{j}</math>, deci pentru astfel de vectori proprii <math>v=(v_1,\dots,v_n),</math> <math>\sum_{i=1}^n v_i = 0</math>.

Un graf regulat de gradul ''k'' este conex [[dacă și numai dacă]] valoarea proprie ''k'' are [[multiplicitate]]a unu. Condiția „numai dacă” este o consecință a {{ill-wd| Q1564541||teoremei Perron–Frobenius}}.<ref name="Cvetkovic"/>

Fie ''G'' un graf ''k''-regulat cu diametrul ''D'' și valorile proprii ale matricei de adiacență <math>k=\lambda_0 >\lambda_1\geq \cdots\geq\lambda_{n-1}</math>. Dacă ''G'' nu este bipartit, atunci<ref>{{en icon}} Gregory Quenell, ''Spectral diameter estimates for k-regular graphs'', ''Advances in Mathematics'', 106(1):122–148, 1994</ref>
: <math>D\leq \frac{\log{(n-1)}}{\log(\lambda_0/\lambda_1)}+1. </math>

== Generare ==
Există algoritmi rapizi pentru a enumera, până la izomorfism, toate grafurile regulate cu un grad și un număr dat de noduri.<ref>{{en icon}} {{cite journal| last=Meringer | first=Markus | year=1999 | title=Fast generation of regular graphs and construction of cages | journal=Journal of Graph Theory | volume=30 | issue=2 | pages=137&ndash;146 | doi= 10.1002/(SICI)1097-0118(199902)30:2<137::AID-JGT7>3.0.CO;2-G| url=http://www.mathe2.uni-bayreuth.de/markus/pdf/pub/FastGenRegGraphJGT.pdf}}</ref>

== Note ==
<references responsive/>

== Bibliografie ==
* {{en icon}} {{Citation | last=Nash-Williams | first=Crispin
| title=Valency Sequences which force graphs to have Hamiltonian Circuits 
| series=University of Waterloo Research Report | publisher=University of Waterloo 
| place=Waterloo, Ontario | year=1969 }}

== Legături externe ==
* {{commonscat-inline|Regular graphs}}
* {{en icon}} {{MathWorld|urlname=RegularGraph|title=Regular Graph}}
* {{en icon}} {{MathWorld|urlname=StronglyRegularGraph|title=Strongly Regular Graph}}
* {{en icon}} [http://www.mathe2.uni-bayreuth.de/markus/reggraphs.html GenReg] software and data by Markus Meringer.

{{Portal|Matematică}}

{{Clase de grafuri}}

[[Categorie:Grafuri|Regulat]]