Graafid ja matemaatiline loogika eksamimaterjal
tsüklite olemasolu, sidususe näitajad
Lühima tee leidmine laiuti otsimise teel:
o Olgu kaalutud suunatud graaf, mille tipud on nummerdatud
naturaalarvudega 1, 2, ... , , kaalud on kaarte pikkused
o Moodustame kaks × -maatriksit ja
o Maatriksi elemendid näitavad seni leitud lühima tee pikkust
tipust tippu . Maatriksi elemendid näitavad tee esimest
vahetippu (kuhu tuleb tipust tippu saamiseks esimesena minna)
o Välimise tsükli esimesel etapil vaadeldakse 1-sammulisi teid, teisel
2-sammulisi, kolmandal 3-sammulisi jne
Laiuti otsingu algoritm sisaldab 4 tsüklit ja nõuab n 4 sammu
Laiuti otsimise korrektsus:
o Peale algoritmi täitmist on väärtuseks lühima tee pikkus tipust
tippu ja väärtuseks sellise tee teise tipu number
o Tsükli invariant: Iga = 1, 2, ..
annaabi.ee 
