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 ${\displaystyle n}$ wierzchołkach oznacza się przez ${\displaystyle K_{n}}$^[1]. Niektóre źródła podają, że litera ${\displaystyle K}$ 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 ${\displaystyle n}$ wierzchołkach posiada ${\displaystyle {\tfrac {n(n-1)}{2}}}$ (lub ${\displaystyle {\tbinom {n}{2}}}$) krawędzi (${\displaystyle n}$ boków i ${\displaystyle {\tfrac {n(n-3)}{2}}}$ przekątnych wielokąta).
• Pełny graf stopnia ${\displaystyle n}$ jest grafem regularnym stopnia ${\displaystyle n-1.}$
• Wszystkie grafy pełne są swoimi klikami.
• Żaden z grafów pełnych stopnia co najmniej ${\displaystyle 5}$ nie jest planarny (wynika z twierdzenia Kuratowskiego).

Przykłady

Poniżej przedstawione zostały pełne grafy o liczbie wierzchołków od ${\displaystyle 1}$ do ${\displaystyle 8{:}}$

• 
  ${\displaystyle K_{1}}$
• 
  ${\displaystyle K_{2}}$
• 
  ${\displaystyle K_{3}}$
• 
  ${\displaystyle K_{4}}$
• 
  ${\displaystyle K_{5}}$
• 
  ${\displaystyle K_{6}}$
• 
  ${\displaystyle K_{7}}$
• 
  ${\displaystyle K_{8}}$

Przypisy

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.

Kontrola autorytatywna (graf nieskierowany):

• LCCN: sh85029361
• GND: 4188588-0
• J9U: 987007545781605171

Encyklopedie internetowe:

• Britannica: topic/complete-graph