Regulaarne graaf

Regulaarne graaf on graaf mille kõikide tippude valentsused (astakud) on võrdsed, st iga tipp omab sama arv naabertippe.

Regulaarsuse valents on graafi invariant ning tähistatakse . Kõikide graafide hulgas domineerivad mitteregulaarsed, regulaarsete osakaal on kaduvväike. Kuna regulaarsete graafide raames võib esineda ka teisi regulaarsusi, siis nimetagem siin esimest valentsregulaarsuseks.

Valentsuse (astaku) järgi klassifitseeritult koosneb: 0-regulaarne (tühi graaf) isoleeritud tippudest; 1-regulaarne isoleeritud servadest; 2-regulaarne isoleeritud ringidest (tsüklitest, vöödest) või kujutab tervikuna ringi. 3-regulaarset nimetatakse ka kuupgraafiks.

 Täiendavad regulaarsused 
Graafi regulaarsus on tippude ja/või servade omadus olla teatud mõttes ühesugused. On olemas erinevaid regulaarsusi.
 Valentsregulaarne graaf, mille iga tipu kõikide naabertippude kaugus on d, on d-distantsregulaarne. Näites esitatud 3-valentsregulaarne graaf on ka 2-distantsregulaarne.
 Valentsregulaarne graaf, mille kõik tipud kuuluvad vöösse ümbermõõduga d on d-vööregulaarne. Näiteks, valentsregulaarne Peterseni graaf on 5-vööregulaarne.
 Valentsregulaarne graaf, mille kõik tipud kuuluvad klikki võimsusega n on n-klikkregulaarne. Näiteks, Peterseni graafi täiend on 4-klikkregulaarne ning koosneb neljast lõikuvast 4-klikist.
 Valentsregulaarne graaf, mille iga naabertippude paar omab  ühist naabrit ja iga mittenaabertippude paar omab  ühist naabrit on tugevregulaarne. Näiteks, Peterseni graaf on ka tugevregulaarne.

Need regulaarsused on hästi väljaloetavad graafi semiootilisest mudelist.

 Seoseid regulaarsuste vahel 
 Valentsregulaarsete graafide hulgas on distants-, vöö-, klikk- ja tugevregulaarsete osakaal kaduvväike.
 Valentsregulaarse graafi  täiend  on valentsregulaarne.
 Vööregulaarse graafi  täiend  on klikkregulaarne, ja vastupidi.
 Klikkregulaarse graafi klikid võivad olla kas komponentsed, sidusad või lõikuvad.
 m-aluselise graafi  täiend  on võrdsete aluste n puhul n-klikkregulaarne, mittelõikuvate n-klikkide arvuga m.
 Tugevregulaarse graafi  sidus täiend  on tugevregulaarne.

 Regulaarsus ja sümmeetria 
Ka graafi sümmeetria puhul on tegemist ühesuguste kordumisega ehk ekvivalentsusklassidega. Graafi sümmeetria on nö "kõige tugevam regulaarsus". Tippudest sümmeetriline (transitiivne) graaf on valents-, distants- ja vööregulaarne (või klikkregulaarne) . Samal ajal on valentsregulaarne graaf väga harvadel juhtudel sümmeetriline. Ka tugevregulaarne graaf ei pea olema sümmeetriline.

 Kirjandust 
 Harary, F. Graph Theory. Addison-Wesley, 1969.
 Tevet, J.-T. Graafi varjatud külgi. S.E.R.R. 2009. ISBN 9789949213108
 Ashay Dharwadker, A., Pirzada, B. Graph Theory, Proc. Institute of Mathematics, Amazon Books, 2011. ISBN 1466254998

 Vaata ka 
Graafi klikk ja vöö

Kategooria:Graafiteooria