Graafi täiend

Peterseni graaf (vasakul) ja selle täiend (paremal)

Graafi $G$ täiend on graaf $\bar{G}$, mis omab servi vaid nende tipupaaride vahel kus graaf $G$ neid ei oma. Graafide $G$ ja $\bar{G}$ ühend on täisgraaf.

Graafi $G$ ja selle täiendi $\bar{G}$ tipuorbiidid langevad kokku. Graafi $G$ servaorbiidid langevad kokku täiendi $\bar{G}$ "mitteservade" orbiitidega.

Graafi struktuuri uurimisel on kasulik kõrvutada graaf $G$ tema täiendiga $\bar{G}$. Graafi, mis on isomorfne oma täiendiga on isetäienduv graaf.

Kirjandust

• Buldas, A., Laud, P., Villemson, J. (2003), Graafid, TÜ kirjastus