Grafikon-kiegészítés

A gráf komplementere ( inverz gráf ) egy olyan gráf , amelynek csúcskészlete megegyezik az adott gráféval , de amelyben két nem egybeeső csúcs akkor és csak akkor szomszédos, ha nem szomszédos -ben . $G'$ $G$ $G$

Formálisan egy egyszerű gráfhoz és - csúcsainak összes kételemű részhalmazához - a komplementet úgy definiáljuk, mint egy pár - egy gráf az eredeti csúcshalmazzal és a teljes gráfból ezek eltávolításával kapott élek halmazával. az adott grafikonon. $G=(V,E)$ $K={\mathcal {P}}(V^{2})$ $G'$ $(V,K\setminus E)$

Egy üres gráf (amely csak csúcsokat tartalmaz, éleket nem tartalmaz) komplementere egy teljes gráf , és fordítva. A gráf független halmaza a gráf komplementerében lévő klikk , és fordítva. A háromszög nélküli gráf komplementere nem tartalmaz karmokat .

Az önkomplementer gráf olyan gráf, amely izomorf a komplementerével. A kográfok olyan gráfok, amelyek egyetlen pontból összeállíthatók független unió és komplement művelettel. A kográfok önkomplementer gráfok családját alkotják – bármely kográf komplementere egy másik (esetleg az eredetitől eltérő) kográf.

Irodalom

Harari F. Gráfelmélet. — 2. kiadás. - M. : URSS, 2003. - 295 p. — ISBN 5-354-00301-6 .