Regularni graf je v teoriji grafov graf brez zank in večkratnih povezav v katerem ima vsaka točka enako število sosednjih točk, oziroma vsaka točka ima enako stopnjo ali valenco. Za regularni usmerjeni graf mora veljati tudi strožji pogoj, da je stopnja vstopajočih povezav enaka stopnji odtekajočih povezav.[1] Regularni graf s točkami stopnje k se imenuje regularni graf stopnje k ali k-regularni graf.

Osnovne značilnosti

uredi

Regularne grafe stopnje vsaj 2 je lahko razvrstiti: 0-regularni graf vsebuje nepovezane točke, 1-regularni graf vsebuje nepovezane povezave, 2-regularni graf pa vsebuje nepovezane cikle.

3-regularni graf je znan kot kubični graf, 4-regularni graf pa kot kvartični graf.

Krepkoregularni graf je regularni graf kjer ima vsak sosednji par točk enako število skupnih sosednjih točk l, in vsak nesosednji par točk enako število skupnih sosednjih točk n. Najmanjša grafa, ki sta regularna, ne pa tudi krepkoregularna, sta cikel in cirkulantni graf na 6-tih točkah.

Polni graf   je krepkoregularen za vsak  .

Nash-Williamsov izrek pravi, da ima vsak k-regularni graf na   točkah Hamiltonov cikel.

Pogoja za obstoj

uredi

Dobro je znano, da sta potrebna in zadostna pogoja za obstoj  -regularnega grafa reda  , da velja   in, da je produkt   sod. Tedaj je lahko skonstruirati regularne grafe z upoštevanjem ustreznih parametrov cirkulantnih grafov.

Algebrske značilnosti

uredi

Naj je A matrika sosednosti grafa. Potem je graf regularen, če in samo če je   lastni vektor A.[2] Njegova [flastna vrednost]] bo konstantna stopnja grafa. Lastni vektorji, ki odgovarjajo drugim lastnim vrednostim, so pravokotni na  , tako da za vsak tak lastni vektor   velja  .

Regularni graf stopnje k je povezan, če in samo če ima lastna vrednost k multiplikativnost ena. Pogoj je posledica Perron-Frobeniusovega izreka.[2]

Obstaja tudi kriterij za regularne in povezane grafe: graf je povezan in regularen, če in samo če je matrika enic J, kjer je  , algebra sosednosti grafa, kar pomeni, da je linearna kombinacija potenc A.[3]

Naj je G k-regularni graf s premerom D in lastnimi vrednostmi matrike sosednosti  . Če G ni dvodelen, velja:

 [4]

Število neizomorfnih regularnih grafov

uredi

Število možnih neizomorfnih povezanih k-regularnih grafov na n točkah podaja naslednja razpredelnica:

n 3 4 5 6 7 8 9 10 11 12
  A002851 A006820 A006821 A006822 A014377 A014378 A014381 A014382 A014384  
0 1 1 1 1 1 1 1 1 1 1
1 0 0 0 0 0 0 0 0 0 0
2 0 0 0 0 0 0 0 0 0 0
3 0 0 0 0 0 0 0 0 0 0
4 1 0 0 0 0 0 0 0 0 0
5 0 1 0 0 0 0 0 0 0 0
6 2 1 1 0 0 0 0 0 0 0
7 0 2 0 1 0 0 0 0 0 0
8 5 6 3 1 1 0 0 0 0 0
9 0 16 0 4 0 1 0 0 0 0
10 19 59 60 21 5 1 1 0 0 0
11 0 265 0 266 0 6 0 1 0 0
12 85 1544 7848 7849 1547 94 9 1 1 0
13 0 10778 0 367860 0 10786 0 10 0 1
14 509 88168 3459383 21609300 21609301 3459386 88193 540 13 1
15 0 805491 0 1470293675 0 1470293676 0 805579 0 17
16 4060 8037418 2585136675 113314233808 733351105934 733351105935 113314233813 2585136741 8037796 4207
17 0 86221634 0 9799685588936 0 0 9799685588961 0 86223660
18 41301 985870522 2807105250897
19 0 11946487647 0 0 0 0
20 5104891 152808063181
21 0 2056692014474 0 0 0 0
22 7319447 28566273166527

Ustvarjanje regularnih grafov

uredi

Regularni grafi se lahko ustvarjajo s programom GenReg.[5]

Glej tudi

uredi

Sklici

uredi
  • Chen, Wai-Kai (1997), Graph Theory and its Engineering Applications, World Scientific, ISBN 978-981-02-1859-1
  • Curtin, Brian (2005), »Algebraic characterizations of graph regularity conditions«, Designs, Codes and Cryptography, 34 (2–3): 241–248, doi:10.1007/s10623-004-4857-4, MR 2128333
  • Cvetković, Dragoš M.; Doob, M.; Sachs, H. (1998), Spectra of Graphs: Theory and Applications (3. rd rev. enl. izd.), New York: Wiley
  • Meringer, Markus (1999), »Fast generation of regular graphs and construction of cages« (PDF), Journal of Graph Theory, 30 (2): 137–146, doi:10.1002/(SICI)1097-0118(199902)30:2<>1.0.CO;2-G
  • Quenell, Gregory (1992), Spectral diameter estimates for k-regular graphs (PDF) (v angleščini), arhivirano iz prvotnega spletišča (PDF) dne 6. januarja 2014, pridobljeno 29. junija 2016

Zunanje povezave

uredi