Körgráf

matematikai fogalom a gráfelméletben

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

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ő
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

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.

Jegyzetek szerkesztés

  1. Some simple graph spectra. win.tue.nl
  2. Fertin, Guillaume; Raspaud, André & Reed, Bruce (2004), "Star coloring of graphs", Journal of Graph Theory 47 (3): 163–182, DOI 10.1002/jgt.20029