Eĝo (grafeteorio)

El Vikipedio, la libera enciklopedio
(Alidirektita el Latero (grafeteorio))
Saltu al: navigado, serĉo
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

En grafeteorio, eĝolatero estas unu el la fundamentaj unuoj el kiuj grafeoj estas formitaj.

Sendirekta grafeo konsistas el aro de verticoj kaj aro de eĝoj kiuj tiam estas neordigitaj paroj de verticoj. Orientita grafeo konsistas el aro de verticoj kaj aro de eĝoj kiuj tiam estas arkoj - ordigitaj duopoj de verticoj.

Al eĝo povas esti asignita valoro aŭ pezo. Minimuma generanta arbo estas subgrafeo kiu kunkonektas ĉiujn verticojn de la grafeo sed enhavas nur parton de la eĝoj, la eĝoj estas elektitaj tiel ke sumo de iliaj pezoj estas minimuma. La alia komuna uzo de la pezoj estas la vojaĝa tempo aŭ kosto por la vojaĝa komiza problemo.

Ekzemplo[redakti | redakti fonton]

6n-graf.svg
Sendirektita grafeo kun 6 verticoj kaj 7 eĝoj
Multigraph.svg
Eblas esti pluraj eĝoj inter la samaj verticoj (ruĝaj),

ebas esti buklo, eĝo kiu ligas verticon al si (blua)

Directed graph.svg
eĝoj de direktita grafeo havas direktojn,

montritajn per sagoj

Weighted K4.svg
Eĝoj kun pezoj
La minimuma generanta arbo de grafeo estas montrita per grasaj eĝoj
Diversaj variantoj de direktaj kaj sendirektaj eĝoj

Vidu ankaŭ[redakti | redakti fonton]

Eksteraj ligiloj[redakti | redakti fonton]