Malfermi la ĉefan menuon

Ciklo (grafeteorio)

DifinojRedakti

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 cikloRedakti

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

ReferencojRedakti

  1. BAVANT, Marc. (2003) Matematika Vortaro kaj Oklingva Leksikono. Prago: Kava-Pech. ISBN 80-85853-65-5.