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 r(G). 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.


Pilt:0-regulární graf na 6 vrcholech.png|0-valentsregulaarne graaf
Pilt:1-regulární graf na 6 vrcholech.svg|1-valentsregulaarne graaf
Pilt:2-regulární graf na 6 vrcholech.svg|2-valentsregulaarne graaf
Pilt:3-regular graph2.svg|3-valentsregulaarne graaf


## 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  a\geqslant 0 ühist naabrit ja iga mittenaabertippude paar omab  b\geqslant 1  ü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 r(G) täiend  \overline G  on valentsregulaarne.
* *Vööregulaarse* graafi  G  täiend  \overline G  on *klikkregulaarne*, ja vastupidi.
* Klikkregulaarse graafi klikid võivad olla kas *komponentsed, sidusad* või *lõikuvad*.
* *m*-aluselise graafi  G  täiend  \overline G  on võrdsete aluste *n* puhul *n-klikkregulaarne*, mittelõikuvate *n-klikkide* arvuga *m*.
* Tugevregulaarse graafi  G  sidus täiend  \overline G  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öö