Transitiivne graaf

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. 

Kategooria:Graafiteooria