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.. Regularni graf s točkami stopnje k se imenuje regularni graf stopnje k ali k-regularni graf.
Osnovne značilnosti
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
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
Naj je A matrika sosednosti grafa. Potem je graf regularen, če in samo če je lastni vektor A.. 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.
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..
Naj je G k-regularni graf s premerom D in lastnimi vrednostmi matrike sosednosti . Če G ni dvodelen, velja:
.
Število neizomorfnih regularnih grafov
Š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 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
Regularni grafi se lahko ustvarjajo s programom GenReg..
Glej tudi
naključni regularni graf krepkoregularni graf Mooreov graf kletka visokoiregularni graf kubični graf kvartični graf kvintični graf
Sklici
Viri
Zunanje povezave
GenReg – program in podatki, Meringer, Markus
Kategorija:Družine grafov