Körgráf

A Wikipédiából, a szabad enciklopédiából
Körgráf
6 csúcsú körgráf
6 csúcsú körgráf

Csúcsok száma n
Élek száma n
Átmérő \left \lfloor n/2 \right \rfloor
Derékbőség n
Kromatikus szám 2, ha n páros
3, ha n páratlan
Élkromatikus szám 2, ha n páros
3, ha n páratlan
Automorfizmusok 2n (darab)
Spektrum {2 cos(2 k π / n); k=1, ... ,n}[1]
Egyéb 2-reguláris
Jelölés C_n

A körgráf egy olyan gráf, amely egy körből áll, és más élt nem tartalmaz. Az n csúcsú körgráfot C_n szimbólummal szokás jelölni. Az élek száma megegyezik a csúcsok számával, és minden csúcs fokszáma 2.

Tulajdonságok[szerkesztés]

Minden körgráf

Alkalmazások[szerkesztés]

Számítógép-hálózatok topológiájaként választják bizonyos esetekben a körgráfot. Ilyen kontextusban beszélnek gyűrű topológiáról is.

  1. Some simple graph spectra. win.tue.nl