Dopełnienie grafu

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

Konstrukcja formalna

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

• $V_{H}=V_{G}$ i
• $E_{H}=E_{K}\setminus E_{G},$ gdzie $K^{n}(V_{K},E_{K})$ jest grafem pełnym rozmiaru $n=|V_{G}|,$ $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 $G={\overline {G}}.$

Graf Petersena (po lewej) i jego dopełnienie

Zobacz też

• graf (matematyka)
• teoria grafów