Cikla grafeo

En grafeoteorio, cikla grafeo aŭ simpla cikla grafeo estas grafeo kiu konsistas de sola vojo (ciklo). En aliaj vortoj, iu kvanto da verticoj estas koneksa kiel fermita ĉeno. La cikla grafeo kun n verticoj estas skribata kiel Cn. La kvanto de lateroj en Cn egalas al kvanto de verticoj n. Ĉiu vertico havas gradon 2; tio estas, ĉiu vertico havas akurate du laterojn koneksajn al ĝi.

Ciklo kun para kvanto de verticoj estas nomata kiel para ciklo; ciklo kun nepara kvanto de verticoj estas nomata kiel nepara ciklo.

 Propraĵoj 
Cikla grafeo estas:
 Koneksa grafeo
 2-regula grafeo
 Eŭlera grafeo
 Grafeo de Hamilton
 2-vertice kolorigebla, se kaj nur se ĝi havas paran kvanton de verticoj. Pli ĝenerale, grafeo estas 2-vertice kolorigebla se kaj nur se ĝi ne enhavas neparajn ciklojn.
 2-latere kolorigebla se kaj nur se ĝi havas paran kvanton de verticoj
 3-vertice kolorigebla kaj 3-latere kolorigebla, por ĉiu kvanto de verticoj
 Unua distanca grafeo

Ĉar cikla grafeo povas esti desegnita kiel regula plurlatero, la aŭtomorfia grupo (simetrioj) de n-ciklo estas la samaj kiel tiuj de regula plurlatero kun n lateroj, la duedra grupo de ordo 2n. Aparte, tie ekzistas simetrioj metantaj ĉiun unu donitan verticon al ĉiu la alia donita vertico, kaj ĉiun unu donitan lateron al ĉiu la alia donita latero, tiel la n-ciklo estas simetria grafeo.

 Direktita cikla grafeo 

Direktita cikla grafeo estas direktita versio de cikla grafeo, kun ĉiuj lateroj orientitaj en la sama direkto.

En orientita grafeo, subaro de lateroj kiu enhavas almenaŭ unu lateron (arkon) de ĉiu direktita ciklo estas nomata kiel retrokupla arka aro. Simile, subaro de verticoj kiu enhavas almenaŭ unu verticon de ĉiu direktita ciklo estas nomata kiel retrokupla vertica aro.

En direktita cikla grafeo ĉiu vertico havas eneniran duongradon 1 kaj eliran duongradon 1.

Direktitaj ciklaj grafeoj estas grafeoj de Cayley por ciklaj grupoj.

 Vidu ankaŭ 

 Ciklo (grafeoteorio)
 Plena dukolora grafeo
 Voja grafeo
 Plena grafeo
 Nulgrafeo

 Eksteraj ligiloj 
 Cikla grafeo je MathWorld
 Signoj kaj elvolvaĵo de Luca Trevisan

Kategorio:Grafeteorio