Cyklický graf - Cycle graph - Wikipedia

Cyklický graf
	Cyklický graf délky 6
Vrcholy	n
Hrany	n
Obvod	n
Automorfismy	2n (Dn)
Chromatické číslo	3 pokud n je zvláštní; 2 jinak
Chromatický index	3 pokud n je zvláštní; 2 jinak
Spektrum	{2 cos (2kπ/n); k = 1, ..., n}
Vlastnosti	2-pravidelné; Vrchol-tranzitivní; Edge-tranzitivní; Jednotková vzdálenost; Hamiltonian; Eulerian
Zápis
	Tabulka grafů a parametrů

v teorie grafů, a graf cyklu nebo kruhový graf je graf který se skládá z jediného cyklus, nebo jinými slovy, určitý počet vrcholů (alespoň 3, pokud je graf jednoduchý ) připojené v uzavřeném řetězci. Graf cyklu s n vrcholy se nazývají C_n. Počet vrcholů v C_n se rovná počtu hrany a každý vrchol má stupeň 2; to znamená, že každý vrchol má přesně dva okraje dopadající na něj.

Terminologie

Je jich mnoho synonyma pro „cyklický graf“. Tyto zahrnují jednoduchý cyklický graf a cyklický graf, ačkoli druhý termín je používán méně často, protože může odkazovat také na grafy, které pouze nejsou acyklický. Mezi teoretiky grafů cyklus, polygonnebo n-gon jsou také často používány. Termín n-cyklus se někdy používá v jiných nastaveních.^[2]

Cyklus se sudým počtem vrcholů se nazývá an rovnoměrný cyklus; cyklus s lichým počtem vrcholů se nazývá an lichý cyklus.

Vlastnosti

Graf cyklu je:

Dvoubarevný, právě když má sudý počet vrcholů
2-pravidelné
2-vrcholový barevný, právě když má sudý počet vrcholů. Obecněji je graf bipartitní kdyby a jen kdyby nemá žádné liché cykly (Kőnig, 1936).
Připojeno
Eulerian
Hamiltonian
A graf jednotkové vzdálenosti

Navíc:

Jak mohou být cyklické grafy tažené tak jako pravidelné mnohoúhelníky, symetrie z n-cykly jsou stejné jako u běžného mnohoúhelníku s n strany, dihedrální skupina objednávky 2n. Zejména existují symetrie, které berou jakýkoli vrchol na jakýkoli jiný vrchol a jakoukoli hranu na jakoukoli jinou hranu, takže n-cyklus je symetrický graf.

Podobně jako Platonické grafy, cyklické grafy tvoří kostry dihedra. Jejich duály jsou dipólové grafy, které tvoří kostry hosohedra.

Graf řízeného cyklu

Směrovaný cyklický graf délky 8

A graf řízeného cyklu je řízená verze cyklického grafu se všemi hranami orientovanými ve stejném směru.

V řízený graf, sada hran, která obsahuje alespoň jednu hranu (nebo oblouk) z každého směrovaného cyklu se nazývá a sada zpětného oblouku. Podobně se sada vrcholů obsahujících alespoň jeden vrchol z každého směrovaného cyklu nazývá a sada vrcholů zpětné vazby.

Graf řízeného cyklu má jednotný stupeň 1 a jednotný stupeň 1.

Grafy směrovaného cyklu jsou Cayleyovy grafy pro cyklické skupiny (viz např. Trevisan).

Viz také

Reference

^ Některá jednoduchá grafová spektra. win.tue.nl
^ „Problém 11707“. Amer. Matematika. Měsíční. 120 (5): 469–476. Květen 2013. doi:10,4169 / amer.math.monthly.120.05.469. JSTOR 10,4169 / amer.math.monthly.120.05.469.

externí odkazy

Weisstein, Eric W. "Cyklický graf". MathWorld. (diskuse o grafech 2 pravidelných cyklů a skupinově teoretickém konceptu cyklické diagramy )
Luca Trevisan, Postavy a rozšíření.

[1] Některá jednoduchá grafová spektra. win.tue.nl

[2] „Problém 11707“. Amer. Matematika. Měsíční. 120 (5): 469–476. Květen 2013. doi:10,4169 / amer.math.monthly.120.05.469. JSTOR 10,4169 / amer.math.monthly.120.05.469.

[1]

[2]