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