Przejdź do zawartości

Graf pełny

Z Wikipedii, wolnej encyklopedii

Graf pełnygraf 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

[edytuj | edytuj kod]
  • 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

[edytuj | edytuj kod]

Poniżej przedstawione zostały pełne grafy o liczbie wierzchołków od do

Przypisy

[edytuj | edytuj kod]
  1. Reinhard Diestel: Graph Theory. Nowy Jork: 2000, s. 3. ISBN 0-387-95014-1.
  2. David Gries, Fred B. Schneider: A Logical Approach to Discrete Math. Springer-Verlag, 1993, s. 436.
  3. Thomas L. Pirnot: Mathematics All Around. Addison Wesley, 2000, s. 154. ISBN 978-0-201-30815-0.