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 | |
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ésMinden körgráf
- összefüggő.
- 2-reguláris.
- tartalmaz Hamilton-kört.
- tartalmaz Euler-kört.
- 1-szívós
- kromatikus száma páros
esetén 2, egyébként 3
- élkromatikus száma páros
esetén 2, egyébként 3
- lerajzolható egység hosszúságú élekkel, gyufagráf
- csúcstranzitív
- csillagkromatikus száma
, ha n=5, egyébként
.[2]
Alkalmazások
szerkesztésSzá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- ↑ Some simple graph spectra. win.tue.nl
- ↑ Fertin, Guillaume; Raspaud, André & Reed, Bruce (2004), "Star coloring of graphs", Journal of Graph Theory 47 (3): 163–182, DOI 10.1002/jgt.20029
🔥 Top keywords: Kezdőlap2024-es labdarúgó-Európa-bajnokságCristiano RonaldoSpeciális:KeresésGrúziaA magyar egészségügy napjaLabdarúgó-Európa-bajnokságSzlovéniaJan OblakPepe (labdarúgó, 1983)Semmelweis IgnácJúlius 1.A köztisztviselők és kormánytisztviselők napja2020-as labdarúgó-Európa-bajnokságMarine Le PenDiogo CostaPortugál labdarúgó-válogatottMagyarországKylian Mbappé2024. évi nyári olimpiai játékokYouTubeLionel MessiSpeciális:Friss változtatásokSárkányok háza2026-os labdarúgó-világbajnokságBelgiumAz Európai Unió tagállamaiZimány LindaMagyar Péter (jogász)Labdarúgó-világbajnokságZichyújfaluZac EfronOrszághívószámok listájaLamine YamalMagyar labdarúgó-válogatottPortugáliaSzamárköhögésMagyar névnapok listája dátum szerintFrancia labdarúgó-válogatott