Běžný graf

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 8. října 2019; kontroly vyžadují 3 úpravy .

Regulární (homogenní) graf je graf , jehož stupně všech vrcholů jsou stejné, to znamená, že každý vrchol má stejný počet sousedů. Stupeň pravidelnosti je graf invariantní a označuje se . Nedefinováno pro nepravidelné grafy . Pravidelné grafy představují zvláštní výzvu pro mnoho algoritmů. $r(G)$ $r(G)$

Regulární graf s vrcholy stupně $k$ se nazývá $k$ - regulární nebo regulární graf stupně $k$ .

Regulární grafy stupně nejvýše dva lze snadno klasifikovat: 0-regulární graf se skládá z izolovaných vrcholů ( nulový graf ), 1-regulární graf se skládá z izolovaných hran a 2-regulární graf se skládá z nesouvislých cyklů .

3-běžný graf je také známý jako kubický graf .

Silně pravidelný graf je pravidelný graf, pro který existuje a takový, že libovolné dva sousední vrcholy mají společné sousedy a kterékoli dva nesousedící vrcholy mají společné sousedy. Nejmenšími grafy, které jsou pravidelné, ale ne silně pravidelné, jsou cyklický graf a cirkulační graf na šesti vrcholech. $\lambda$ $\mu$ $\lambda$ $\mu$

Kompletní graf je silně pravidelný pro všechny . $K_{m}$ $m$

Nash-Williamsova věta [ říká, že každý $k$ - regulární graf na $2k + 1$ vrcholech má Hamiltonovský cyklus .

0-běžný graf
1-běžný graf
2-běžný graf

Algebraické vlastnosti

Nechť A je matice sousednosti grafu. Pak je graf regulární právě tehdy, když existuje vlastní vektor A [1] . Jeho vlastní číslo bude konstantní mocninou grafu. Vlastní vektory odpovídající jiným vlastním číslům jsou ortogonální , takže pro vlastní vektory máme . ${\textbf {j}}=(1,\tečky,1)$ ${\textbf {j))$ $v=(v_{1},\tečky ,v_{n})$ $\sum _{{i=1}}^{n}v_{i}=0$

Regulární graf stupně k je souvislý právě tehdy, když vlastní číslo k má násobnost 1 [1] .

Další kritérium pro pravidelnost a spojitost grafu: graf je souvislý a pravidelný právě tehdy, když je matice J с v algebře sousednosti grafu [2] . $J_{{ij}}=1$

Nechť G je k-regulární graf o průměru D a s vlastními hodnotami matice sousednosti . Pokud G není bipartitní: $k=\lambda _{0}>\lambda _{1}\geq \dots \geq \lambda _{{n-1}}$

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

kde

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

Generace

Pomocí programu GenReg lze vygenerovat pravidelný graf. [5]

Viz také

Náhodný pravidelný graf
Silně pravidelný graf
hrabě Moore
Buňka

Poznámky

↑ 1 2 D. M. Cvetkovich, M. Dub a H. Sachs, Graph Spectrum: Theory and Applications, 3. vydání, New York: Wylie, 1998.
↑ Curtin, Brian (2005), Algebraické charakterizace podmínek pravidelnosti grafu , Designs, Codes and Cryptography vol. 34 (2-3): 241–248 , DOI 10.1007/s10623-004-4857-4
↑ Gregory Quenell. Odhady spektrálního průměru pro k-regulární grafy.
↑ Fanoušek RK Chung. Teorie spektrálních grafů. - American Mathematical Society, 1997. - (CBMS). — ISBN 0821803158 .
↑ M. Mehringer, "Teorie grafů", 1999, 30, 137.

Odkazy

Weisstein, Eric W. Regular Graph ve Wolfram MathWorld .
Weisstein, Eric W. Strongly Regular Graph ve Wolfram MathWorld .
Program GenReg a data od Markuse Mehringera.
Nash-Williams, Crispin (1969), Valenční sekvence, které nutí grafy mít Hamiltonovské okruhy, Výzkumná zpráva University of Waterloo , Waterloo, Ontario: University of Waterloo