Utfyllende graf

I grafteori er den komplementære grafen eller den inverterte grafen til en enkel graf en enkel graf som har de samme hjørnene og slik at to forskjellige hjørner av er tilstøtende hvis og bare hvis de ikke ligger ved siden av . $G$ $H$ $H$ $G$

Den utfyllende grafen skal ikke forveksles med den utfyllende i betydningen settteori . Faktisk forblir settet med hjørner av G uendret.

Eiendommer

Komplementet til komplementet er den originale grafen.
Summen av en graf og dens komplement er den komplette grafen .
En klikk i en graf er et uavhengig sett i den komplementære grafen.
De selvkomplementære grafeneselvkomplementær graf er at grafene er isomorfe til deres komplementære.
De cographs er definert spesielt ved en komplemente operasjon.

Merknader og referanser

(i) Eric W. Weisstein , " Graph Complement " på MathWorld