Ciklični graf

Cycle graph
Neusmerjeni ciklični graf
Točke	n
Povezave	n
Notranji obseg	n
Avtomorfizem	2n (Dn)
Kromatično število	3 kadar jen neparen 2 kadar je n paren
Kromatični indeks	3 kadar je n neparen 2 kadar je n paren
Spekter	$2 \cos(2k\pi /n);$ $k=1, ... ,n$
Značilnosti	2-regularen točkovno-prehoden povezavno-prehoden z enotsko razdaljo Hamiltonov Eulerjev
Označba	$C_n$

Ciklični graf (oznaka $C_n \,$ za graf z $n \,$ vozlišči) je v teoriji grafov graf, ki ga sestavlja samo en cikel. To pomeni, da je nekaj vozlišč povezanih v zaprto verigo. Pri cikličnem grafu lahko vedno določimo število vozlišč $n \,$ in zaradi tega označujemo takšen graf z $C_n \,$. Število vozlišč je enako številu povezav, vsako vozlišče ima stopnjo 2.

Značilnosti cikličnega grafa

Ciklični graf je

• povezljiv
• 2-regularen
• Eulerjev
• Hamiltonov
• 2 vozliščno obarvljiv
• 2 povezavno obarvljiv
• 3 vozliščno in 3 povezavno obarvljiv
• z enotno povezavo

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 graf
• pot v grafu

Zunanje povezave

• Ciklični graf (neusmerjeni) na MathWorld (v angleščini)
• Teorija grafov (v angleščini)