Transitiivne graaf

Allikas: Vikipeedia
Jump to navigation Jump to search

Graafiteoorias eristatakse tippudest transitiivset graafi ja servadest transitiivset graafi. Suunatud graafide puhul on kasutusel ka veel kolmas transitiivsuse tähendus.

Tippudest transitiivne graaf on graaf kus selle iga kahe tipu ja vahel eksisteerib automorfism mis kujutab tipu tipuks . Teisisõnu, graaf on tippudest transitiivne siis kui selle automorfismide rühm töötab transitiivselt oma tippude hulgal . Sedasama transitiivsust nimetatakse ka automorfismide transitiivsuseks, graafi sümmeetriaks, orbiidiks ning graafi struktuursest aspektist tippude positsiooniks graafis .

Servadest transitiivne graaf on graaf kus selle iga kahe serva ja vahel eksisteerib automorfism mis kujutab serva servaks . Teisisõnu, graaf on servadest transitiivne siis kui selle automorfismide rühm töötab transitiivselt oma servade hulgal . Sedasama transitiivsust nimetatakse ka graafi sümmeetriaks, orbiidiks ning graafi struktuursest aspektist servade positsiooniks graafis .

Tippudest ja servadest transitiivsed on näiteks Peterseni graaf, Heawoodi graaf ja Hamiltoni graaf. Servadest transitiivseks jääb ka Petrseni graafi täiend kuid mitte Heawoodi ja Hamiltoni graafi täiendid. Folkmani graaf on vaid servadest transitiivne.

Suunatud graafide puhul tähendab transitiivsus tippudevahelist suunatud servade ühesuunalist jada.