Teljes gráf

A Wikipédiából, a szabad enciklopédiából.

Megtekintett lap

Ez az utolsó megtekintett változat (összes); elfogadva: 2009. október 19.

Pontosság

megtekintett

Teljes gráf

K₅ – az 5 csúcsú teljes gráf
Névadó	Kazimierz Kuratowski
Csúcsok száma	n
Élek száma	n(n-1)/2
Sugár
Átmérő	1
Kromatikus szám	n
Élkromatikus szám
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.

[szerkesztés] 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