Szabályos grafikon

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2019. október 8-án felülvizsgált verziótól ; az ellenőrzések 3 szerkesztést igényelnek .

A szabályos (homogén) gráf olyan gráf , amelynek minden csúcsának foka egyenlő, azaz minden csúcsnak ugyanannyi szomszédja van. A szabályosság foka egy gráfinvariáns , és jelölése . Undefined szabálytalan grafikonokhoz . A szabályos gráfok számos algoritmus számára különleges kihívást jelentenek. $r(G)$ $r(G)$

$A k$ fokú csúcsokkal rendelkező reguláris gráfot $k$ - szabályosnak , vagy $k$ fokú reguláris gráfnak nevezzük .

A legfeljebb kettő fokozatú reguláris gráfok könnyen osztályozhatók: a 0-reguláris gráf izolált csúcsokból ( null-gráf ), az 1-es reguláris gráf izolált élekből, a 2-reguláris gráf pedig diszjunkt ciklusokból áll .

A 3-reguláris gráfot kocka gráfnak is nevezik .

Az erősen szabályos gráf egy olyan reguláris gráf, amelyre létezik, és olyan, hogy bármely két szomszédos csúcsnak közös szomszédja van, és bármely két nem szomszédos csúcsnak közös szomszédja van. A legkisebb reguláris, de nem erősen szabályos gráfok a ciklikus gráf és a hat csúcsú körgráf . $\lambda$ $\mu$ $\lambda$ $\mu$

A teljes gráf erősen szabályos bármely . $K_{m}$ $m$

A Nash-Williams tétel kimondja, hogy minden $2k$ $+$ $1$ csúcson lévő $k$ - reguláris gráfnak van egy Hamilton-ciklusa .

0-reguláris gráf
1-szabályos gráf
2-reguláris gráf

Algebrai tulajdonságok

Legyen A a gráf szomszédsági mátrixa . Ekkor a gráf akkor és csak akkor szabályos, ha van A sajátvektor [1] . A saját száma lesz a gráf állandó hatványa. A többi sajátértéknek megfelelő sajátvektorok ortogonálisak , így a sajátvektorokhoz . ${\textbf {j}}=(1,\pontok ,1)$ ${\textbf {j))$ $v=(v_{1},\pontok,v_{n})$ $\sum _{{i=1}}^{n}v_{i}=0$

Egy k fokú reguláris gráf akkor és csak akkor kapcsolódik össze , ha a k sajátérték multiplicitása 1 [1] .

A gráf szabályosságának és konnektivitásának másik kritériuma: a gráf akkor és csak akkor összefüggő és szabályos, ha a J с mátrix a gráf [ szomszédsági algebrájában van [2] . $J_{{ij}}=1$

Legyen G egy D átmérőjű k-szabályos gráf a szomszédsági mátrix sajátértékeivel . Ha G nem kétrészes: $k=\lambda _{0}>\lambda _{1}\geq \dots \geq \lambda _{{n-1}}$

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

ahol

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

Generáció

Szabályos gráf generálható a GenReg programmal. [5]

Lásd még

Véletlenszerű szabályos gráf
Erősen szabályos gráf
Moore gróf
Sejt

Jegyzetek

↑ 1 2 D. M. Cvetkovich, M. Dub és H. Sachs, Graph Spectrum: Theory and Applications, 3. kiadás, New York: Wylie, 1998.
↑ Curtin, Brian (2005), Algebraic characterizations of graph regularity conditions , Designs, Codes and Cryptography vol. 34 (2-3): 241–248 , DOI 10.1007/s10623-004-4857-4
↑ Gregory Quenell. Spektrális átmérő becslések k-reguláris gráfokhoz.
↑ Fan RK Chung. Spektrális gráf elmélet. - American Mathematical Society, 1997. - (CBMS). — ISBN 0821803158 .
↑ M. Mehringer, "Graph Theory", 1999, 30, 137.

Linkek

Weisstein, Eric W. Regular Graph at Wolfram MathWorld .
Weisstein, Eric W. Erősen szabályos gráf a Wolfram MathWorldnél .
GenReg program és adatok Markus Mehringertől.
Nash-Williams, Crispin (1969), Valencia szekvenciák, amelyek a gráfokat Hamiltoni áramkörökre kényszerítik, University of Waterloo Research Report , Waterloo, Ontario: University of Waterloo