Graf pełny
Graf pełny – graf prosty, nieskierowany, w którym dla każdej pary węzłów istnieje krawędź je łącząca.
Graf pełny o wierzchołkach oznacza się przez [1]. Niektóre źródła podają, że litera pochodzi od niemieckiego słowa komplett[2], lecz niemiecki termin vollständiger Graph, oznaczający graf pełny, nie zawiera nawet tej litery. Inne źródła stwierdzają, że tę notację przyjęto w uznaniu zasług Kazimierza Kuratowskiego dla teorii grafów[3].
Własności grafów pełnych
- Pełny graf o wierzchołkach posiada (lub ) krawędzi ( boków i przekątnych wielokąta).
- Pełny graf stopnia jest grafem regularnym stopnia
- Wszystkie grafy pełne są swoimi klikami.
- Żaden z grafów pełnych stopnia co najmniej nie jest planarny (wynika z twierdzenia Kuratowskiego).
Przykłady
Poniżej przedstawione zostały pełne grafy o liczbie wierzchołków od do
Przypisy
- p
- d
- e
Najważniejsze pojęcia |
więcej... |
---|---|
Wybrane klasy grafów |
|
Algorytmy grafowe | |
problemy grafowe | |
Inne zagadnienia |
- Britannica: topic/complete-graph