Dopełnienie grafu
Wygląd
Dopełnienie grafu (ang. complement of graph) – 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 [1].
Konstrukcja formalna
[edytuj | edytuj kod]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
[edytuj | edytuj kod]- 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ż
[edytuj | edytuj kod]Przypisy
[edytuj | edytuj kod]- ↑ Reinhard Diestel: Graph Theory. Nowy Jork: 2000, s. 4. ISBN 0-387-95014-1.