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.

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

Seoseid regulaarsuste vahel

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

Vaata ka

Graafi klikk ja vöö