Dopełnienie grafu

Szablon:Dopracować Dopełnienie grafu (Szablon:Ang.) – graf $\bar{G},$ zawierający te same wierzchołki co graf $G,$ natomiast pomiędzy wierzchołkami grafu $\bar{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=\bar{G}.$

Graf Petersena (po lewej) i jego dopełnienie

Zobacz też

• graf (matematyka)
• teoria grafów