Ciklo (grafeoteorio)

Ciklo en grafeoteorio estas tia simpla ĉeno, ke la du finverticoj estas la sama vertico.

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

 Difinoj 
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.

 Kovro de grafeo per ciklo 
En sia artikolo pri la sep pontoj en Königsberg en 1736, per kiu laŭ multaj li iniciatis grafeoteorion, 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.). 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 , kaj determini ĉu ĝi ekzistas estas NP-kompleta problemo.. 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..

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..

 Grafeklasoj, kiu difiniĝas per ciklo 
Kelkaj gravaj klasoj de grafeoj difiniĝas per siaj cikloj.
 Dukolora grafeo estas grafeo sen ciklo kun nepara nombro da verticoj.
 Cikla grafeo estas grafeo, kiu entute estas unu ciklo.
 Kordeca grafeo estas grafeo tia, ke ne induktita ciklo el ĝi estas pli longa ol 3 verticoj.
 Direkta sencikla grafeo
  estas grafeo tia, ke ne induktita ciklo aŭ ĝia komplemento kun nepara longeco pli longa ol 3
 Kvazaŭarbaro estas sendirekta grafeo, kies ĉiu koneksa komponento havas alpenaŭ unu ciklon
 Koneksega grafeo estas direkta grafeo tia, ke ĉiu eĝo apartenas al iu ciklo
 Sentriangula grafeo estas grafeo sen 3-vertica ciklo

 Referencoj 

Kategorio:Grafeteorio