Graafi täiend

Allikas: Vikipeedia
Peterseni graaf (vasakul) ja selle täiend (paremal)

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

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 | muuda lähteteksti]

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