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

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

Graafi ja selle täiendi tipuorbiidid langevad kokku. Graafi servaorbiidid langevad kokku täiendi "mitteservade" orbiitidega.

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

Kirjandust

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