![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/e/e1/Cube_graph.png/640px-Cube_graph.png&w=640&q=50)
Graf regulat
graf la care fiecare nod are același număr de vecini / From Wikipedia, the free encyclopedia
Î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 Km 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.