Säännöllinen kaavio

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 8. lokakuuta 2019 tarkistetusta versiosta . tarkastukset vaativat 3 muokkausta .

Säännöllinen (homogeeninen) graafi on graafi , jonka kaikkien kärkien asteet ovat yhtä suuret, eli jokaisessa kärjessä on sama määrä naapureita. Säännöllisyyden aste on kaavion invariantti ja sitä merkitään . Määrittelemätön epäsäännöllisille kaavioille . Säännölliset kaaviot ovat erityinen haaste monille algoritmeille. $r(G)$ $r(G)$

Säännöllistä kuvaajaa, jolla on k-asteen kärjet, $kutsutaan$ k $-$ säännölliseksi tai säännölliseksi k-asteen $graafiksi$ .

Korkeintaan kahden asteen säännölliset graafit on helppo luokitella: 0-säännöllinen graafi koostuu eristetyistä pisteistä ( null-graph ), 1-säännöllinen graafi koostuu eristetyistä reunoista ja 2-säännöllinen graafi koostuu hajaantuneista sykleistä .

3-säännöllinen graafi tunnetaan myös kuutiograafina .

Voimakkaasti säännöllinen graafi on säännöllinen graafi, jolle on olemassa ja sellainen, että kahdella vierekkäisellä pisteellä on yhteiset naapurit ja kahdella ei vierekkäisellä pisteellä on yhteiset naapurit. Pienimmät graafit, jotka ovat säännöllisiä, mutta eivät voimakkaasti säännöllisiä, ovat syklinen graafi ja kiertografiikka kuudella pisteellä. $\lambda$ $\mu$ $\lambda$ $\mu$

Täydellinen kaavio on vahvasti säännöllinen mille tahansa . $K_{m}$ $m$

Nash-Williamsin lause sanoo, että jokaisella $k$ -säännöllisellä graafilla $2k + 1$ -pisteissä on Hamiltonin sykli .

0-säännöllinen kaavio
1-säännöllinen kaavio
2-säännöllinen kaavio

Algebralliset ominaisuudet

Olkoon A graafin vierekkäisyysmatriisi . Tällöin kuvaaja on säännöllinen silloin ja vain, jos siinä on ominaisvektori A [1] . Sen oma luku on graafin vakiopotenssi. Muita ominaisarvoja vastaavat ominaisvektorit ovat ortogonaalisia , joten ominaisvektoreille meillä on . ${\textbf {j}}=(1,\pisteet ,1)$ ${\textbf {j))$ $v=(v_{1},\pisteet ,v_{n})$ $\sum _{{i=1}}^{n}v_{i}=0$

Säännöllinen k -asteen kuvaaja on yhdistetty silloin ja vain, jos ominaisarvon k kerrannaisluku on 1 [1] .

Toinen graafin säännöllisyyden ja liitettävyyden kriteeri: graafi on yhdistetty ja säännöllinen silloin ja vain jos matriisi J с on graafin [2] viereisyysalgebrassa ] . $J_{{ij}}=1$

Olkoon G k-säännöllinen kuvaaja, jonka halkaisija on D ja vierekkäisyysmatriisin ominaisarvot . Jos G ei ole kaksiosainen: $k=\lambda _{0}>\lambda _{1}\geq \dots \geq \lambda _{{n-1}}$

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

missä

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

Sukupolvi

Säännöllinen graafi voidaan luoda GenReg-ohjelmalla. [5]

Katso myös

Satunnainen säännöllinen kaavio
Hyvin säännöllinen kaavio
Kreivi Moore
Cell

Muistiinpanot

↑ 1 2 D. M. Cvetkovich, M. Dub ja H. Sachs, Graph Spectrum: Theory and Applications, 3. painos, New York: Wylie, 1998.
↑ Curtin, Brian (2005), Graafisten säännönmukaisuusehtojen algebralliset karakterisoinnit , Designs, Codes and Cryptography osa 34 (2-3): 241–248 , DOI 10.1007/s10623-004-4857-4
↑ Gregory Quenell. Spektrihalkaisijaestimaatit k-säännöllisille kaavioille.
↑ Tuuletin RK Chung. Spektrigrafiikkateoria. - American Mathematical Society, 1997. - (CBMS). — ISBN 0821803158 .
↑ M. Mehringer, "Graph Theory", 1999, 30, 137.

Linkit

Weisstein, Eric W. Regular Graph at Wolfram MathWorld .
Weisstein, Eric W. Strongly Regular Graph at Wolfram MathWorld .
GenReg- ohjelma ja tiedot Markus Mehringeriltä.
Nash-Williams, Crispin (1969), Valenssisekvenssit, jotka pakottavat kaavioihin Hamiltonin piirejä, Waterloon yliopiston tutkimusraportti , Waterloo, Ontario: Waterloon yliopisto