Ciklo (grafeteorio): Malsamoj inter versioj
| [nekontrolita versio] | [nekontrolita versio] |
Enhavo forigita Enhavo aldonita
8zu (diskuto | kontribuoj) difino |
8zu (diskuto | kontribuoj) riĉigo |
||
Linio 2:
'''Ciklo''' estas tia simpla ĉeno, ke la du finpunktojn estas la sama vertico<ref name=":0">{{Citaĵo el libro|titolo=Matematika Vortaro kaj Oklingva Leksikono|familia nomo=Bavant|persona nomo=Marc|jaro=2003|eldoninto=Kava-Pech|loko=Prago|isbn=80-85853-65-5|aŭtoroligilo=Marc Bavant}}</ref>.
== Difinoj ==
Estas pluraj eblaj difinoj por ciklo. '''Fermita vojo''' estas vico da verticoj tia, ke la unua kaj lasta vertico estas la sama, kaj ĉiu vertico estas najbara al la antaŭa kaj sekva vertico, per la ĝusta direkto se la grafeo estas direkta.
'''Simpla ciklo''' estas '''fermita vojo''' tia, ke la eĝoj en la ĉeno ne ripetas. Oni ofte alprenas simplecon kiam oni uzas la terminon "ciklo".
== 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 ankaŭ nomiĝas [[Arbo (grafeteorio)|arbo]]
* [[Perfekta 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]]
| |||