Betöltett grafikonok
A betöltött gráf olyan D = (V, X) orientált gráf, amelynek ívkör-készlete meghatározott függvényt definiál. amelyet súlyfüggvénynek neveznek.
Az ív fölötti ábra (lásd az 5. ábrát) az ívsúly (az ív ára).
Jelölés: D betöltett, D-irányú gráf bármely pálya esetében l (Π) az P-ös pályán bejövő ívek hosszának összege (minden ív számozása annyiszor számít, ahogy az Π ösvénybe lép).
Az l mennyiséget az úthossznak nevezik.
Ha az 1-es súlyok közül választunk, akkor a be nem töltött grafikonra érkezünk.
Egy útvonal a betöltött orientált gráfból a csúcsból v és a csúcs között w. ahol v ¹ w. az úgynevezett minimális. ha a legrövidebb hosszúságú.
A betöltött gráf minimális útvonalát hasonlóan definiáljuk.
Bemutatjuk az n sorrend ívhosszakának mátrixát (C). és
Minimális útvonalak tulajdonságai egy betöltött orientált gráfban
1) Ha az "ív", akkor a minimális útvonal (útvonal) egy egyszerű lánc;
2) ha a minimális útvonal (útvonal), akkor az "i, j. Az útvonal (útvonal) is minimális;
3) ha - az útvonalak (útvonalak) közötti minimális útvonal (útvonal) v-ről w-re. amely legfeljebb k +1 íveket (éleket) tartalmaz, majd - a legkisebb útvonalat (útvonalat) a v-től az u-ig az útvonalak (útvonalak) között, amelyek legfeljebb k íveket (éleket) tartalmaznak.