Dopełnienie grafu
Z Wikipedii
Niniejszy artykuł jest częścią cyklu teoria grafów.
|
Najważniejsze pojęcia Wybrane klasy grafów Algorytmy grafowe Zagadnienia przedstawiane jako problemy grafowe Inne zagadnienia |
edytuj ten szablon |
Dopełnieniem grafu (ang. complement of graph) G nazywamy graf , zawierający te same wierzchołki co graf G, 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 G.
[edytuj] Konstrukcja formalna
Dla grafu G(VG,EG) o wierzchołkach VG i krawędziach EG, jego dopełnieniem określa się graf H(VH,EH) taki, że:
- VH = VG i
- , gdzie Kn(VK,EK) jest grafem pełnym rozmiaru n = | VG | , VK = VG.
[edytuj] 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.
Def. Graf jest samodopełniający się gdy .
Zobacz też: Teoria grafów, graf (matematyka).