Ciklo (grafeteorio)

El Vikipedio, la libera enciklopedio
Jump to navigation Jump to search
La artikolo estas parto de serio pri grafeteorio.




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 grafeteorio


vidi  diskuti  redakti

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

Difinoj[redakti | redakti fonton]

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[redakti | redakti fonton]

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

Referencoj[redakti | redakti fonton]

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