Cikla grafeo

El Vikipedio, la libera enciklopedio
Saltu al: navigado, serĉo
Cikla grafeo
Plia nomo Simpla cikla grafeo
Bildo
Cikla grafeo de 6 verticoj
Verticoj n
Lateroj n
Aŭtomorfioj 2n
Koloriga nombro 3 se n estas nepara,
2 se n estas para
Propraĵoj 2-regula,
vertico-transitiva,
latero-transitiva,
unua distanca
v  d  r
Information icon.svg

En grafeteorio, cikla grafeosimpla 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[redakti | redakti fonton]

Cikla grafeo estas:

Ĉ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[redakti | redakti fonton]

Direktita cikla grafeo de longo 8

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ŭ[redakti | redakti fonton]

Eksteraj ligiloj[redakti | redakti fonton]