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 $G$ kus selle iga kahe tipu $v_1$ ja $v_2$ vahel eksisteerib automorfism mis kujutab tipu $v_1$ tipuks $v_2$. Teisisõnu, graaf $G$ on tippudest transitiivne siis kui selle automorfismide rühm $AutG$ töötab transitiivselt oma tippude hulgal $V$. Sedasama transitiivsust nimetatakse ka automorfismide transitiivsuseks, graafi sümmeetriaks, orbiidiks ning graafi struktuursest aspektist tippude positsiooniks $\mathrm{\Omega }V$ graafis $G$.

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

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.