mały|Graf Petersena (po lewej) i jego dopełnienie
Dopełnienie grafu () – graf zawierający te same wierzchołki co graf natomiast pomiędzy wierzchołkami grafu istnieje krawędź wtedy i tylko wtedy, gdy pomiędzy tymi wierzchołkami nie istnieje krawędź w grafie .
Konstrukcja formalna Dla grafu o wierzchołkach i krawędziach jego dopełnieniem określa się graf taki że: i gdzie jest grafem pełnym rozmiaru
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
Zobacz też graf (matematyka) teoria grafów
Przypisy
Linki zewnętrzne [dostęp 2025-10-12].
Kategoria:Teoria grafów