Graafi täiend

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.

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

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