Eĝo (grafeteorio)
| 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 |
En grafeoteorio, eĝo aŭ latero estas unu el la fundamentaj unuoj, 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 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 | redakti fonton] Sendirektita grafeo kun 6 verticoj kaj 7 eĝoj |
 Eblas esti pluraj eĝoj inter la samaj verticoj (ruĝaj), ebas esti buklo, eĝo kiu ligas verticon al si (blua) |
 eĝoj de direktita grafeo havas direktojn, montritajn per sagoj |
 Eĝoj kun pezoj |
Vidu ankaŭ
[redakti | redakti fonton]- Glosaro de grafeoteorio
- Latero (geometrio)
- Dudirekta grafeo povas enhavi specialajn specojn de eĝoj
- Arko-transitiva grafeo
- Senlatera grafeo