Regularni graf
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:

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 
 

Družine grafov
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 vsajje lahko razvrstiti :regularni graf vsebuje nepovezane točke ,regularni graf vsebuje nepovezane povezave ,regularni graf pa vsebuje nepovezane cikle . 3 - regularni graf je znan kot kubični graf ,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 natih 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 : 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 Družine grafov