Mine sisu juurde

Regulaarne graaf

Allikas: Vikipeedia

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

[muuda | muuda lähteteksti]

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

[muuda | muuda lähteteksti]
  • 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

[muuda | muuda lähteteksti]

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.

  • 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

Graafi klikk ja vöö