Ciklični graf

Ciklični graf
Neusmerjeni ciklični graf
Točke	n
Povezave	n
Premer	n/2, če je n sod (n − 1)/2, če je n lih
Notranji obseg	n
Avtomorfizem	2n (Dn)
Kromatično število	2, če je n sod 3, če je n lih
Kromatični indeks	2, če je n sod 3, če je n lih
Spekter	$2\cos(2k\pi /n);$ $k=1,...,n$
Značilnosti	ravninski 2-regularen točkovnoprehoden povezavnoprehoden z enotsko razdaljo Eulerjev Hamiltonov simetričen Cayleyjev
Označba	$C_{n}\,$

Ciklični graf (oznaka $C_{n}\,$ za graf z $n\,$ točkami) je v teoriji grafov graf, ki ga sestavlja samo en cikel. To pomeni, da je nekaj točk povezanih v zaprto verigo. Pri cikličnem grafu se lahko vedno določi število točk $n\,$ in zaradi tega se takšen graf označuje s $C_{n}\,$. Število točk je enako številu povezav, vsaka točka ima stopnjo 2.

Značilnosti cikličnega grafa

Ciklični graf je

• ravninski
• 2-povezavnopobarvljiv
• 2-regularen
• 2-točkovnopobarvljiv
• 3-točkovno in 3-povezavnoobarvljiv
• povezan
• Eulerjev
• Hamiltonov
• z enotsko razdaljo
• simetričen
• Cayleyjev

Usmerjeni ciklični graf z dolžino 8.

Usmerjeni ciklični graf

Usmerjeni ciklični graf ima vse povezave usmerjene v isto smer.

Glej tudi

• polni dvodelni graf
• polni graf
• ničelni graf
• pot
• cirkulantni graf

Zunanje povezave

• Weisstein, Eric Wolfgang. »Cycle Graph«. MathWorld.
• Teorija grafov (angleško)