Eĝo (grafeoteorio)

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

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 la 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 
 150x150px  Sendirektita grafeo kun 6 verticoj kaj 7 eĝoj 150x150px En grafeo povas ekzisti pluraj eĝoj inter la samaj verticoj (ruĝaj) kaj buklo, eĝo kiu ligas verticon kun si mem (blua) 150x150px  eĝoj de direktita grafeo havas direktojn,
montritajn per sagoj 150x150px  Eĝoj kun pezoj
eta|300px|maldekstra|La minimuma generanta arbo de grafeo estas montrita per grasaj eĝoj
eta|450px|maldekstra|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 


Kategorio:Grafeteorio