Teljes gráf

A Wikipédiából, a szabad enciklopédiából
10 szög
K10 – a 10 csúcsú teljes gráf
K10 – a 10 csúcsú teljes gráf

Névadó Kazimierz Kuratowski
Csúcsok száma n
Élek száma
Sugár
Átmérő
Derékbőség
Kromatikus szám n
Élkromatikus szám n, ha n páratlan
n − 1, ha n páros
Automorfizmusok n! (Sn)
Spektrum
Egyéb reguláris
Jelölés Kn

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 -nel jelöljük Kazimierz Kuratowski lengyel matematikus emlékére.

Tulajdonságok[szerkesztés]

  • reguláris, minden csúcsának fokszáma .
  • összesen élt tartalmaz.
  • a Kuratowski-tétel szerint síkbarajzolható gráf nem tartalmazhat a gráffal topologikusan izomorf részgráfot.
  • az (n+1)-szimplex éleit adja.

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

További információk[szerkesztés]