Dopełnienie grafu

Dopełnienie grafu (ang. complement of graph) – graf ${\displaystyle {\overline {G}},}$ zawierający te same wierzchołki co graf ${\displaystyle G,}$ natomiast pomiędzy wierzchołkami grafu ${\displaystyle {\overline {G}}}$ istnieje krawędź wtedy i tylko wtedy, gdy pomiędzy tymi wierzchołkami nie istnieje krawędź w grafie ${\displaystyle G}$^[1].

Konstrukcja formalna

Dla grafu ${\displaystyle G(V_{G},E_{G})}$ o wierzchołkach ${\displaystyle V_{G}}$ i krawędziach ${\displaystyle E_{G},}$ jego dopełnieniem określa się graf ${\displaystyle H(V_{H},E_{H}),}$ taki że:

• ${\displaystyle V_{H}=V_{G}}$ i
• ${\displaystyle E_{H}=E_{K}\setminus E_{G},}$ gdzie ${\displaystyle K^{n}(V_{K},E_{K})}$ jest grafem pełnym rozmiaru ${\displaystyle n=|V_{G}|,}$ ${\displaystyle V_{K}=V_{G}.}$

Własności

• Dopełnieniem n-wierzchołkowego grafu regularnego stopnia k jest n-wierzchołkowy graf regularny stopnia n-k-1.
• Dopełnieniem grafu pełnego jest graf nie zawierający krawędzi.
• Graf jest samodopełniający się gdy ${\displaystyle G={\overline {G}}.}$

Graf Petersena (po lewej) i jego dopełnienie

Zobacz też

• graf (matematyka)
• teoria grafów

Przypisy

1. Reinhard Diestel: Graph Theory. Nowy Jork: 2000, s. 4. ISBN 0-387-95014-1.