Grafic regulat - Regular graph

În teoria graficelor , un grafic regulat este un grafic în care fiecare vârf are același număr de vecini; adică fiecare vârf are același grad sau valență. Un grafic direcționat regulat trebuie să satisfacă, de asemenea, condiția mai puternică în care gradul inferior și cel inferior al fiecărui vârf sunt egale unul cu celălalt. Un grafic regulat cu vârfuri de grad se numește grafic -regular sau grafic regulat de grad . De asemenea, din lema strângerii de mână , un grafic regulat conține un număr par de vârfuri cu grad impar. ${\ displaystyle k}$${\ displaystyle k}$${\ displaystyle k}$

Graficele regulate de grad cel mult 2 sunt ușor de clasificat: un grafic 0-regulat constă din vârfuri deconectate, un grafic 1 regulat constă din margini deconectate, iar un grafic 2-regulat constă dintr-o unire disjunctă de cicluri și lanțuri infinite.

Un grafic cu 3 reguli este cunoscut sub numele de grafic cub .

Un grafic puternic regulat este un grafic regulat în care fiecare pereche adiacentă de vârfuri are același număr l de vecini în comun și fiecare pereche non-adiacentă de vârfuri are același număr n de vecini în comun. Cele mai mici grafice care sunt regulate, dar nu foarte regulate, sunt graficul ciclului și graficul circulant pe 6 vârfuri.

Graficul complet este puternic regulat pentru orice . ${\ displaystyle K_ {m}}$${\ displaystyle m}$

O teoremă a lui Nash-Williams spune că fiecare grafic regulat pe 2 k  + 1 vârfuri are un ciclu hamiltonian . ${\ displaystyle k}$

• 

  0-grafic regulat

• 

  1-grafic regulat

• 

  2-grafic regulat

• 

  3-grafic regulat

Existenţă

Este bine cunoscut faptul că condițiile necesare și suficiente pentru a exista un grafic regulat al ordinii sunt acelea și asta este egal. ${\ displaystyle k}$${\ displaystyle n}$${\ displaystyle n \ geq k + 1}$${\ displaystyle nk}$

Dovadă: după cum știm, un grafic complet are fiecare pereche de vârfuri distincte conectate între ele printr-o margine unică. Deci muchiile sunt maxime în graficul complet și numărul de muchii sunt și gradul este aici . Deci . Acesta este minimul pentru un anumit anume . De asemenea, rețineți că dacă un grafic obișnuit are ordine, atunci numărul de muchii este așa trebuie să fie par. În acest caz, este ușor să construim grafice regulate luând în considerare parametrii adecvați pentru graficele circulante . ${\ displaystyle {\ binom {n} {2}} = {\ dfrac {n (n-1)} {2}}}$${\ displaystyle n-1}$${\ displaystyle k = n-1, n = k + 1}$${\ displaystyle n}$${\ displaystyle k}$${\ displaystyle n}$${\ displaystyle {\ dfrac {nk} {2}}}$${\ displaystyle nk}$

Proprietăți algebrice

Să A fi matricea de adiacenta a unui grafic. Apoi , graficul este regulat dacă și numai dacă este un vector propriu al A . Valoarea sa proprie va fi gradul constant al graficului. Vectorii proprii corespunzători altor valori proprii sunt ortogonali , deci pentru acești vectori proprii avem . ${\ displaystyle {\ textbf {j}} = (1, \ dots, 1)}$${\ displaystyle {\ textbf {j}}}$${\ displaystyle v = (v_ {1}, \ dots, v_ {n})}$${\ displaystyle \ sum _ {i = 1} ^ {n} v_ {i} = 0}$

Un grafic regulat al gradului k este conectat dacă și numai dacă valoarea proprie k are o multiplicitate. Direcția „numai dacă” este o consecință a teoremei Perron – Frobenius .

Există, de asemenea, un criteriu pentru graficele regulate și conectate: un grafic este conectat și regulat dacă și numai dacă matricea celor J , cu , se află în algebra de adiacență a graficului (adică este o combinație liniară de puteri ale lui A ). ${\ displaystyle J_ {ij} = 1}$

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

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

Generaţie

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

Vezi si

• Grafic regulat aleatoriu
• Grafic puternic regulat
• Graficul Moore
• Graficul cuștii
• Grafic foarte neregulat

Referințe

linkuri externe

• Weisstein, Eric W. „Grafic regulat” . MathWorld .
• Weisstein, Eric W. „Grafic puternic regulat” . MathWorld .
• GenReg software - ul și datele de Markus Meringer.
• Nash-Williams, Crispin (1969), Secvențe de valență care forțează graficele să aibă circuite hamiltoniene , Raport de cercetare al Universității din Waterloo, Waterloo, Ontario: Universitatea din Waterloo