Eĝo (grafeteorio)

En grafeoteorio, eĝo aŭ latero estas unu el la fundamentaj unuoj, el kiuj grafeoj estas formitaj.

La artikolo estas parto de serio pri grafeoteorio.

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 pli... 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 grafeoteorio

Sendirekta grafeo konsistas el aro da verticoj kaj aro da eĝoj, kiuj estas neordigitaj paroj de verticoj. Orientita grafeo konsistas el aro da verticoj kaj aro da eĝoj, kiuj 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 problemo de kolportisto.

Ekzemplo

Sendirektita grafeo kun 6 verticoj kaj 7 eĝoj	En grafeo povas ekzisti pluraj eĝoj inter la samaj verticoj (ruĝaj) kaj buklo, eĝo kiu ligas verticon kun si mem (blua)
eĝoj de direktita grafeo havas direktojn, montritajn per sagoj	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ŭ

• Glosaro de grafeoteorio
• Latero (geometrio)
• Dudirekta grafeo povas enhavi specialajn specojn de eĝoj
• Arko-transitiva grafeo
• Senlatera grafeo

Eksteraj ligiloj

• Eric W. Weisstein, Latero de grafeo en MathWorld.