Orbiitgraaf

Orbiitgraaf $G_n$ on graafi $G$ alamgraaf, mille servad $e_{ij}$ vastavad ühe binaarorbiidi ${\mathrm{\Omega }}_n$ elementidele (st tipupaaridele). Orbiitgraafi on nimetatud ka positsioonistruktuuriks.

Orbiitgraafid on olulised atribuudid graafi struktuuri uurimisel, nad toovad esile või avavad graafi $G$ erinevaid "varjatud külgi". Seda just sümmeetriliste või suuri binaarorbiite omavate graafide puhul.

Orbiitgraafide omadusi

• Orbiitgraafide arv võrdub binaarorbiitide arvuga. Nende hulka kuuluvad nii serva- kui ka "mitteserva" orbiidid, st graafi täiendi servaorbiidid.
• Orbiitgraaf on tippudest ja servadest sümmeetriline. Seega on iga orbiitgraaf valents- ja ring- või klikkregulaarne.
• Graafi erinevad orbiitgraafid või erinevate graafide orbiitgraafid võivad osutuda isomorfseteks või langeda kokku.
• Graafi mõni orbiitgraaf võib osutuda isomorfseks graafi endaga,

Näiteks, Folkmani graafil on kuus binaarorbiiti, sh üks serva- ja viis "mitteserva" orbiiti. Selle ühele "mitteserva" orbiidile vastav orbiitgraaf on Peterseni graaf, teisele orbiidile vastav aga selle täiend. Selliseid graafide põimumisi esineb tihti.

Vaatluse all on ka graafi teist ja kõrgemat järku orbiitgraafid, st orbiitgraafide orbiitgraafid. Kõrgemat järku orbiitgraafide indutseerimine on koonduv protsess, see lõpeb alati mõne madalamat järku orbiitgraafi või lähtegraafiga isomorfse graafi esiletuleku või selle taastamisega.

Kirjandust

• Tevet, J.-T. (2001). Semiotic Testing of the Graphs. S.E.R.R., Tallinn
• Tevet, J.-T. (2917). Graafide identifitseerimine. ISBN 9789949816514, S.E.R.R., Tallinn
• Tevet, J.-T. (2017). What is a graph and how to study it. ISBN 9879949817559. S.E.R.R., Tallinn

Vaata ka

• Graafide identifitseerimine
• Graafide semiootiline modelleerimine