Orbiitgraaf

Orbiitgraaf on graafi alamgraaf, mille servad vastavad ühe binaarorbiidi elementidele (st tipupaaridele). Orbiitgraafi on nimetatud ka positsioonistruktuuriks.

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

Orbiitgraafide omadusi

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

Vaata ka