Graafi täiend

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

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

Graafi $G$ ja selle täiendi $\overline G$ tipuorbiidid langevad kokku. Graafi $G$ servaorbiidid langevad kokku täiendi $\overline G$ „mitteservade“ orbiitidega.

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

Kirjandust

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