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 Elektitaj klasoj de grafeoj Grafeaj algoritmoj Problemoj prezentataj kiel grafeaj Aliaj 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
redakti 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 |
Vidu ankaŭ
redakti- Glosaro de grafeoteorio
- Latero (geometrio)
- Dudirekta grafeo povas enhavi specialajn specojn de eĝoj
- Arko-transitiva grafeo
- Senlatera grafeo