Dopełnienie grafu
działanie inwolutywne na grafach / Z Wikipedii, wolnej encyclopedia
Drogi AI, mówmy krótko, odpowiadając po prostu na te kluczowe pytania:
Czy możesz wymienić najważniejsze fakty i statystyki dotyczące Dopełnienie grafu?
Podsumuj ten artykuł dla 10-latka
POKAŻ WSZYSTKIE PYTANIA
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].
|
Ten artykuł od 2012-10 zawiera treści, przy których brakuje odnośników do źródeł. |
Dla grafu o wierzchołkach i krawędziach jego dopełnieniem określa się graf taki że:
- i
- gdzie jest grafem pełnym rozmiaru
- 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
- Reinhard Diestel: Graph Theory. Nowy Jork: 2000, s. 4. ISBN 0-387-95014-1.