Pravidelný graf - Regular graph

v teorie grafů, a běžný graf je graf kde každý vrchol má stejný počet sousedů; tj. každý vrchol má stejné stupeň nebo valence. Pravidelný řízený graf musí také splňovat silnější podmínku, že nezávislý a překonat každého vrcholu jsou navzájem stejné.^[1] Pravidelný graf s vrcholy stupňů ${ displaystyle k}$ se nazývá a ${ displaystyle k}$–Pravidelný graf nebo pravidelný graf stupňů ${ displaystyle k}$. Také z handmaking lemma, pravidelný graf lichého stupně bude obsahovat sudý počet vrcholů.

Pravidelné grafy stupně nejvýše 2 lze snadno klasifikovat: 0-pravidelný graf se skládá z odpojených vrcholů, 1-pravidelný graf se skládá z odpojených hran a 2-pravidelný graf se skládá z disjunktní unie z cykly a nekonečné řetězce.

Pravidelný graf 3 je známý jako a kubický graf.

A silně pravidelný graf je pravidelný graf, kde každá sousední dvojice vrcholů má stejný počet l společných sousedů a každá nesousedící dvojice vrcholů má stejný počet n společných sousedů. Nejmenší grafy, které jsou pravidelné, ale ne příliš pravidelné, jsou graf cyklu a oběhový graf na 6 vrcholech.

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

Věta od Nash-Williams říká, že každý ${ displaystyle k}$–Pravidelný graf zapnutý 2k + 1 vrcholy má a Hamiltonovský cyklus.

• 

  0-pravidelný graf

• 

  1-pravidelný graf

• 

  2-pravidelný graf

• 

  3-pravidelný graf

Existence

Je dobře známo^{[Citace je zapotřebí ]} že nezbytné a dostatečné podmínky pro a ${ displaystyle k}$ pravidelný graf objednávky ${ displaystyle n}$ to existuje ${ displaystyle n geq k + 1}$ a to ${ displaystyle nk}$ je sudý.

Důkaz: Jak víme a kompletní graf má každý pár odlišných vrcholů navzájem spojených jedinečnou hranou. Hrany jsou tedy maximální v celém grafu a počet hran je ${ displaystyle { binom {n} {2}} = { dfrac {n (n-1)} {2}}}$ a objednávka je zde ${ displaystyle n-1}$. Tak ${ displaystyle k = n-1, n = k + 1}$. To je minimum ${ displaystyle n}$ pro konkrétní ${ displaystyle k}$. Všimněte si také, že pokud má nějaký pravidelný graf řád ${ displaystyle k}$ pak počet hran je ${ displaystyle { dfrac {nk} {2}}}$ tak ${ displaystyle nk}$ musí být rovnoměrné. V takovém případě je snadné sestavit pravidelné grafy zvážením vhodných parametrů pro oběhové grafy.

Algebraické vlastnosti

Nechat A být matice sousedství grafu. Pak je graf pravidelný kdyby a jen kdyby ${ displaystyle { textbf {j}} = (1, tečky, 1)}$ je vlastní vektor z A.^[2] Jeho vlastní hodnota bude konstantní stupeň grafu. Vlastní vektory odpovídající jiným vlastní čísla jsou kolmé na ${ displaystyle { textbf {j}}}$, takže pro takové vlastní vektory ${ displaystyle v = (v_ {1}, tečky, v_ {n})}$, my máme ${ displaystyle sum _ {i = 1} ^ {n} v_ {i} = 0}$.

Pravidelný graf stupňů k je připojen právě tehdy, pokud vlastní hodnota k má multiplicitu jeden. Směr „pouze pokud“ je důsledkem Perron – Frobeniova věta.^[2]

Existuje také kritérium pro pravidelné a spojené grafy: graf je spojený a pravidelný tehdy a jen tehdy, když matice jedniček J, s ${ displaystyle J_ {ij} = 1}$, je v sousedská algebra grafu (což znamená, že jde o lineární kombinaci mocnin A).^[3]

Nechat G být k-pravidelný graf s průměrem D a vlastní čísla matice sousedství ${ displaystyle k = lambda _ {0}> lambda _ {1} geq cdots geq lambda _ {n-1}}$. Li G tedy není bipartitní

${ displaystyle D leq { frac { log {(n-1)}} { log ( lambda _ {0} / lambda _ {1})}} + 1.}$^[4]

Generace

Existují rychlé algoritmy pro výčet, až do izomorfismu, všech běžných grafů s daným stupněm a počtem vrcholů.^[5]

Viz také

• Náhodný pravidelný graf
• Silně pravidelný graf
• Mooreův graf
• Klec graf
• Velmi nepravidelný graf

Reference

externí odkazy

• Weisstein, Eric W. "Pravidelný graf". MathWorld.
• Weisstein, Eric W. „Silně pravidelný graf“. MathWorld.
• GenReg software a data od společnosti Markus Meringer.
• Nash-Williams, Crispin (1969), Valenční sekvence, které nutí grafy mít Hamiltonovské obvodyZpráva o výzkumu University of Waterloo, Waterloo, Ontario: University of Waterloo