Ciklo (grafeteorio)

5 ŝanĝoj en ĉi tiu versio atendas kontrolon. La stabila versio estis patrolita je 12 sep. 2019.

Ciklo en grafeteorio estas tia simpla ĉeno, ke la du finverticoj estas la sama vertico[1].

La artikolo estas parto de serio pri grafeoteorio.




Plej gravaj terminoj
grafeo
arbo
subgrafeo
ciklo
kliko
grado de vertico
grado de grafeo


Elektitaj klasoj de grafeoj
plena grafeo
plena dukolora grafeo
kohera grafeo
arbo
grafeo dudividebla
Fenda grafeo
regula grafeo
grafeo de Euler
grafeo de Hamilton
grafeo senrelifa


Grafeaj algoritmoj
A*
Bellman-Ford
Dijkstry
Fleury
Floyd-Warshall
Johnson
Kruskal
Prim
traserĉado de grafeo
en larĝeco
en profundo
plej proksima najbaro


Problemoj prezentataj kiel grafeaj
problemo de vojaĝisto
problemo de ĉina leteristo
problemo de marŝrutigado
problemo de kunigado de geedzoj


Aliaj
kodo de Gray
diagramo de Hasse
kodo de Prüfer


Reprezentado de grafeo Glosaro de grafeoteorio


vidi  diskuti  redakti
Grafeo kun eĝoj kolorigitaj por montri fermitan vojon H–A–B–A–H (verda), simplan ciklon B–D–E–F–D–C–B (blua), kaj simplan ciklon sen ripetaj verticoj H–D–G–H (ruĝa).

Grafeo povas esti ciklohava aŭ sencikla. Koneksa sencikla grafeo nomiĝas arbo.

Difinoj

redakti

Estas pluraj eblaj difinoj por ciklo. Simpla ciklo estas tia simpla ĉeno (ĉeno sen ripetaj eĝoj), ke la unua kaj la lasta vertico estas la sama. Fermita vojo estas ajna ĉeno, kies unua kaj lasta vertico estas la sama. Iuj uzas la vorton "ciklo" nur por simplaj cikloj, kaj aliaj por ĉiuj fermitaj vojoj.

En orientita grafeo, ciklo en kiu la fina rando de ĉiu eĝo estas ankaŭ la komenca rando de la sekva eĝo nomiĝas cirkvito.[1]

Kovro de grafeo per ciklo

redakti

En sia artikolo pri la sep pontoj en Königsberg en 1736, per kiu laŭ multaj li naskis grafeteorion, Leonhard Euler pruvis ke ĉiuj eĝoj de finia grafeo kune formas ciklon precize kiam ĝi estas koneksa krom unuopaj verticoj (tio estas, ĉiuj eĝoj apartenas al unu sama komponanto) kaj ĉiu vertico havas paran gradon. La responda teoremo en orientita grafeo estas, ke ĉiuj eĝoj kune formas unu cirkviton precize kiam la grafeo estas forte koneksa kaj havas egalan nombron da venaj kaj iraj eĝoj ĉe ĉiu vertico. Ambaŭokaze, la ciklo nomiĝas eŭlera vojo. Se ĉiu vertico de finia grafeo havas paran gradon, senkonsidere ĉu ĝi estas koneksa, ekzistas aro de cikloj sen ripetaj verticoj kiuj kune kovras ĉiun eĝon precize unufoje (la teoremo de Veblen.)[2] Kiam koneksa grafeo ne plenumas le kondiĉon de la teoremo de Euler, oni tamen povas trovi minimume longan fermitan vojon kovrantan ĉiun eĝon precize unufoje en polinoma tempo per solvado de la vojkontrola problemo.

La trovo de ciklo kiu kovras precize unufoje ĉiun verticon (anstataŭ la eĝoj) estas multe pli malfacila. Tia ciklo nomiĝas Hamilton-a ciklo, kaj determini ĉu ĝi ekzistas estas NP-kompleta problemo.[3] Oni publikigis multe pri klasoj de grafeoj ĉe kiuj la ekzisto de Hamilton-a ciklo estas garantiita; ekzemplo estas la Teoremo de Ore, ke Hamilton-a ciklo ĉiam troveblas en grafeo, ĉe kiu la sumo de gradoj en ĉiu nesameĝa paro da verticoj almenaŭ egalas la totalan nombron de verticoj en la grafeo.[4]

La konjekto de cikla duobla kovro asertas ke por ĉiu senponta grafeo ekzistas multaro de cikloj sen ripetaj verticoj, kiu kovras ĉiun eĝon precize dufoje. Pruvo aŭ malekzemplo ankoraŭ ne estas trovita.[5]

Grafeklasoj, kiu difiniĝas per ciklo

redakti

Kelkaj gravaj klasoj de grafeoj difiniĝas per siaj cikloj.

Referencoj

redakti
  1. 1,0 1,1 Bavant, Marc. (2003) Matematika Vortaro kaj Oklingva Leksikono. Prago: Kava-Pech. ISBN 80-85853-65-5.
  2. Veblen, Oswald (1912), "An Application of Modular Equations in Analysis Situs", Annals of Mathematics, Second Series 14 (1): 86–94, doi:10.2307/1967604 .
  3. Richard M. Karp (1972), "Reducibility Among Combinatorial Problems", in R. E. Miller and J. W. Thatcher, Complexity of Computer Computations, New York: Plenum, pp. 85–103, http://cgi.di.uoa.gr/~sgk/teaching/grad/handouts/karp.pdf, retrieved 2014-03-12 .
  4. Ore, Ø. (1960), "Note on Hamilton circuits", American Mathematical Monthly 67 (1): 55, doi:10.2307/2308928 .
  5. Jaeger, F. (1985), "A survey of the cycle double cover conjecture", Annals of Discrete Mathematics 27 – Cycles in Graphs, North-Holland Mathematics Studies, 27, pp. 1–12, doi:10.1016/S0304-0208(08)72993-1 .