Regularni graf

Iz Wikipedije, proste enciklopedije
Skoči na: navigacija, iskanje

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 vtopajočih povezav enaka stopnji odtekajočih povezav. Regularni graf s točkami stopnje k se imenuje regularni graf stopnje k ali k-regularni graf.

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.

Krepko regularni 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 krepko regularna, sta cikel in cirkulantni graf na 6-tih točkah.

Polni graf K_{m} je krepko regularen za vsak m.

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

Zunanje povezave[uredi | uredi kodo]