Grafkomplement

Komplementet av en graf ( invers graf ) är en graf som har samma uppsättning hörn som den givna grafen , men där två icke-sammanfallande hörn ligger intill om och endast om de inte ligger intill i .

Formellt, för en enkel graf och  - uppsättningen av alla tvåelements delmängder av dess hörn - definieras komplementet som ett par  - en graf med den ursprungliga uppsättningen av hörn och med en uppsättning kanter som erhålls från hela grafen genom att ta bort dessa i den givna grafen.

Komplementet till en tom graf (som endast innehåller hörn och inga kanter) är en komplett graf och vice versa. En oberoende uppsättning av en graf är en klick i komplementet till grafen, och vice versa. Komplementet till en graf utan trianglar innehåller inte klor .

En självkomplementär graf  är en graf som är isomorf till dess komplement. Kografer definieras som grafer som kan konstrueras från en enda punkt genom en icke-relaterad förenings- och komplementoperation. Kografer bildar en familj av självkomplementerande grafer - komplementet till varje kograf är en annan (möjligen annorlunda från originalet) kograf.

Litteratur