Graficul obișnuit

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 8 octombrie 2019; verificările necesită 3 modificări .

Un grafic regulat (omogen) este un grafic ale cărui grade ale tuturor vârfurilor sunt egale, adică fiecare vârf are același număr de vecini. Gradul de regularitate este un invariant de grafic și este notat cu . Nedefinit pentru grafice neregulate . Graficele obișnuite prezintă o provocare specială pentru mulți algoritmi. $r(G)$ $r(G)$

Un graf regulat cu vârfuri de gradul $k$ se numește $k$ - regulat sau un graf regulat de gradul $k$ .

Graficele regulate de cel mult doi sunt ușor de clasificat: un grafic 0-regular este format din vârfuri izolate ( null-graph ), un graf regulat 1 este format din muchii izolate și un grafic 2-regulat este format din cicluri disjunse .

Un grafic cu 3 regulate este cunoscut și sub denumirea de grafic cubic .

Un graf puternic regulat este un graf regulat pentru care există și astfel încât oricare două vârfuri adiacente au vecini comuni și oricare două vârfuri neadiacente au vecini comuni. Cele mai mici grafice care sunt regulate, dar nu puternic regulate sunt graficul ciclic și graficul circular pe șase vârfuri. $\lambda$ $\mu$ $\lambda$ $\mu$

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

Teorema Nash-Williams afirmă că fiecare $k$ - graf regulat pe $2k + 1$ vârfuri are un ciclu hamiltonian .

0-grafic obișnuit
1-grafic obișnuit
2-grafic obișnuit

Proprietăți algebrice

Fie A matricea de adiacență a graficului . Atunci graficul este regulat dacă și numai dacă există un vector propriu A [1] . Numărul său propriu va fi puterea constantă a graficului. Vectorii proprii corespunzători altor valori proprii sunt ortogonali , deci pentru vectorii proprii avem . ${\textbf {j}}=(1,\dots,1)$ ${\textbf {j))$ $v=(v_{1},\dots ,v_{n})$ $\sum _{{i=1}}^{n}v_{i}=0$

Un grafic regulat de gradul k este conex dacă și numai dacă valoarea proprie k are multiplicitatea 1 [1] .

Un alt criteriu pentru regularitatea și conectivitatea graficului: graficul este conex și regulat dacă și numai dacă matricea J с se află în algebra adiacenței a graficului [2] . $J_{{ij}}=1$

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

$D\leq {\frac {\log {(n-1)}}{\log(k/\lambda )))+1$ [3] [4]

Unde

$\lambda =\max _{{i>0}}\{\mid \lambda _{i}\mid \}$ .

Generație

Un grafic obișnuit poate fi generat cu programul GenReg. [5]

Vezi și

Grafic regulat aleatoriu
Grafic puternic regulat
Contele Moore
Celulă

Note

↑ 1 2 D. M. Cvetkovich, M. Dub și H. Sachs, Graph Spectrum: Theory and Applications, ediția a 3-a, New York: Wylie, 1998.
↑ Curtin, Brian (2005), Caracterizări algebrice ale condițiilor de regularitate a graficului , Designs, Codes and Cryptography vol. 34 (2-3): 241–248 , DOI 10.1007/s10623-004-4857-4
↑ Gregory Quenell. Estimări ale diametrului spectral pentru graficele k-regulate.
↑ Fan RK Chung. Teoria graficelor spectrale. - Societatea Americană de Matematică, 1997. - (CBMS). — ISBN 0821803158 .
↑ M. Mehringer, „Teoria graficelor”, 1999, 30, 137.

Link -uri

Weisstein, Eric W. Regular Graph la Wolfram MathWorld .
Weisstein, Eric W. Strongly Regular Graph la Wolfram MathWorld .
Programul GenReg și date de la Markus Mehringer.
Nash-Williams, Crispin (1969), Valency Sequences care forțează graficele să aibă circuite hamiltoniene, Raportul de cercetare al Universității din Waterloo , Waterloo, Ontario: Universitatea din Waterloo