Teljes gráf

Teljes gráf
K5 – az 5 csúcsú teljes gráf
Névadó	Kazimierz Kuratowski
Csúcsok száma	n
Élek száma	n(n-1)/2
Átmérő	1
Kromatikus szám	n
Automorfizmusok	n! (darab)
Egyéb	reguláris

A teljes gráf olyan egyszerű gráf, amelynek minden csúcsa össze van kötve minden más csúccsal. Az n csúcsú teljes gráfot $K_n$-el jelöljük Kazimierz Kuratowski lengyel matematikus emlékére.

Tulajdonságok

• $K_n$ reguláris, minden csúcsának fokszáma $n-1$
• $K_n$ összesen $\binom{n}{2} = \frac{n(n-1)}{2}$ élet tartalmaz
• a Kuratowski-tétel szerint síkbarajzolható gráf nem tartalmazhat a $K_5$ gráffal topologikusan izomorf részgráfot
• $K_n$ az n-szimplex éleit adja

Az első nyolc teljes gráf az alábbi ábrán látható:

• 

  $K_1$

• 

  $K_2$

• 

  $K_3$

• 

  $K_4$

• 

  $K_5$

• 

  $K_6$

• 

  $K_7$

• 

  $K_8$

Külső hivatkozások

• MathWorld: Complete Graph