Grafkomplement

Komplementet af en graf ( omvendt graf ) er en graf , der har det samme sæt af hjørner som den givne graf , men hvor to ikke-sammenfaldende knudepunkter er tilstødende, hvis og kun hvis de ikke støder op i . $G'$ $G$ $G$

Formelt, for en simpel graf og - sættet af alle to-element undersæt af dens hjørner - er komplementet defineret som et par - en graf med det oprindelige sæt af hjørner og med et sæt kanter opnået fra den komplette graf ved at fjerne disse i den givne graf. $G=(V,E)$ $K={\mathcal {P}}(V^{2})$ $G'$ $(V,K\setminus E)$

Komplementet af en tom graf (der kun indeholder hjørner og ingen kanter) er en komplet graf og omvendt. Et uafhængigt sæt af en graf er en klike i komplementet til grafen og omvendt. Komplementet af enhver graf uden trekanter indeholder ikke kløer .

En selvkomplementær graf er en graf, der er isomorf i forhold til dens komplement. Kografer er defineret som grafer, der kan konstrueres fra et enkelt punkt ved en ikke-relateret forenings- og komplementoperation. Kografer danner en familie af selvkomplementære grafer - komplementet af enhver kograf er en anden (muligvis forskellig fra den originale) kograf.

Litteratur

Harari F. Grafteori. — 2. udgave. - M. : URSS, 2003. - 295 s. — ISBN 5-354-00301-6 .