From Wikipedia, the free encyclopedia
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 Elektitaj klasoj de grafeoj pli...
Grafeaj algoritmoj Problemoj prezentataj kiel grafeaj Aliaj Reprezentado de grafeo Glosaro de grafeoteorio |
Grafeo povas esti ciklohava aŭ sencikla. Koneksa sencikla grafeo nomiĝas arbo.
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]
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]
Kelkaj gravaj klasoj de grafeoj difiniĝas per siaj cikloj.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.