Graafi täiend

Allikas: Vikipeedia
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[muuda | redigeeri lähteteksti]

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