Utfyllingsgraf

Petersen-graf (til venstre) og dens komplementgraf (til høyre).

Som et supplement graf , komplementære graf eller komplement er referert til i den grafteori en bestemt graf , oppnådd fra en gitt graf.

Den komplementære grafen har de samme nodene som den opprinnelige grafen , men skiller seg ut i kantene : Komplementgrafen har nøyaktig de kantene som den originale grafen ikke har.

definisjon

La være en ikke-rettet eller rettet graf uten flere kanter . Den ikke-rettet eller rettet graf uten flere kanter kalles komplementgrafen for om skjæringspunktet mellom og er tomt og foreningen av og${\ displaystyle G_ {1} = (V, E_ {1})}$ ${\ displaystyle G_ {2} = (V, E_ {2})}$${\ displaystyle G_ {1}}$${\ displaystyle E_ {1}}$${\ displaystyle E_ {2}}$${\ displaystyle E_ {1}}$${\ displaystyle E_ {2}}$

• i det ikke-rettede tilfellet settet med alle 2-element delmengder av V resp.
• i den rettede saken, det kartesiske produktet ${\ displaystyle V \ times V}$

resultater.

Komplementgrafen til en gitt graf blir ofte referert til som. Som en selvkomplementær refererer grafer isomorf komplementær til deres grafer. ${\ displaystyle G}$${\ displaystyle {\ overline {G}}}$

kjennetegn

• Komplementet til komplementet til G er selve G.