Vanlig graf

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 8 oktober 2019; kontroller kräver 3 redigeringar .

En vanlig (homogen) graf är en graf vars grader av alla hörn är lika, det vill säga att varje vertex har samma antal grannar. Graden av regularitet är en grafinvariant och betecknas med . Odefinierat för oregelbundna grafer . Regelbundna grafer utgör en särskild utmaning för många algoritmer. $r(G)$ $r(G)$

En vanlig graf med hörn av grad $k$ kallas $k$ - regelbunden , eller en vanlig graf av grad $k$ .

Regelbundna grafer av högst två grader är lätta att klassificera: en 0-reguljär graf består av isolerade hörn ( noll-graf ), en 1-regelbunden graf består av isolerade kanter och en 2-regelbunden graf består av osammanhängande cykler .

En 3-regelbunden graf är också känd som en kubisk graf .

En starkt regelbunden graf är en vanlig graf för vilken det finns och sådan att två angränsande hörn har gemensamma grannar och vilka två icke-angränsande hörn som helst har gemensamma grannar. De minsta graferna som är regelbundna men inte starkt regelbundna är den cykliska grafen och den cirkulerande grafen på sex hörn. $\lambda$ $\mu$ $\lambda$ $\mu$

Den fullständiga grafen är starkt regelbunden för alla . $K_{m}$ $m$

Nash -Williams teorem säger att varje $k$ - regelbunden graf på $2k + 1$ hörn har en Hamiltonsk cykel .

0-vanlig graf
1-vanlig graf
2-vanlig graf

Algebraiska egenskaper

Låt A vara grafens närliggande matris . Då är grafen regelbunden om och bara om det finns en egenvektor A [1] . Dess eget nummer kommer att vara den konstanta styrkan för grafen. Egenvektorerna som motsvarar andra egenvärden är ortogonala , så för egenvektorerna har vi . ${\textbf {j}}=(1,\dots ,1)$ ${\textbf {j))$ $v=(v_{1},\dots ,v_{n})$ $\sum _{{i=1}}^{n}v_{i}=0$

En vanlig graf av grad k kopplas om och endast om egenvärdet k har multipliciteten 1 [1] .

Ett annat kriterium för grafens regelbundenhet och anslutning: grafen är sammankopplad och regelbunden om och endast om matrisen J с finns i den närliggande algebra av grafen [2] . $J_{{ij}}=1$

Låt G vara en k-regelbunden graf med diameter D och med egenvärden för närliggande matris . Om G inte är tvådelad: $k=\lambda _{0}>\lambda _{1}\geq \dots \geq \lambda _{{n-1}}$

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

var

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

Generation

En vanlig graf kan genereras med programmet GenReg. [5]

Se även

Slumpmässig vanlig graf
Starkt regelbunden graf
Greve Moore
Cell

Anteckningar

↑ 1 2 D. M. Cvetkovich, M. Dub och H. Sachs, Graph Spectrum: Theory and Applications, 3:e upplagan, 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. Spektraldiameteruppskattningar för k-regelbundna grafer.
↑ Fan RK Chung. Spektralgrafteori. - American Mathematical Society, 1997. - (CBMS). — ISBN 0821803158 .
↑ M. Mehringer, "Graph Theory", 1999, 30, 137.

Länkar

Weisstein, Eric W. Regular Graph på Wolfram MathWorld .
Weisstein, Eric W. Strongly Regular Graph på Wolfram MathWorld .
GenReg- program och data från Markus Mehringer.
Nash-Williams, Crispin (1969), Valenssekvenser som tvingar grafer att ha Hamiltonian Circuits, University of Waterloo Research Report , Waterloo, Ontario: University of Waterloo