Teoreem lihtahelast: kui graafis G leidub ahel tipust u tippu v, siis leidub graafis G ka lihtahel tipust u tippu v Tippude u ja v vaheliseks kauguseks nimetatakse tippude u ja v vahelise lühima lihtahela pikkust Kinniseks ahelaks nimetatakse ahelat, mis algab ja lõpeb samas tipus Tsükliks nimetatakse kinnist ahelat, kus on vähemalt üks serv ja ükski serv ei kordu Lihttsükliks nimetatakse tsüklit, kus iga sisetipp esineb ainult ühe korra Teoreem lihtahela ja lihttsükli leidumisest: kui graafi iga tipu aste on vähemalt l2, siis leidub graafis lihtahel pikkusega l ja lihttsükkel pikkusega vähemalt l+1 Graafi, milles iga kahe tipu korral leidub neid tippe ühendav (liht)ahel, nimetatakse sidusaks o kui graaf ei ole sidus, siis koosneb ta eraldiseisvatest sidusatest osadest, mida nimetatakse sidusateks komponentideks
tipust i tippu j , siis liigume läbi tipu k . Näide 44 54. ** Floyd-Warshalli algoritmi keerukuse hinnang ja korrektsuse tõestus. [2] Floys-Warshalli algoritmi keerukuse hinnang o Miks leiab Floyd-Warshalli algoritm tõesti lühima võimaliku ahela iga kahe tipu vahel? o Kui lühima ahela i … j suurima indeksiga sisetipp on k, siis on algoritmi varasematel sammudel juba leitud lühimad ahelad i … k ja k … j ning otsitav lühim ahel leitakse seega üles k-ndal sammul. Tõestus o Korrektsuse teoreemi võib sõnastada nii: Iga n korral kehtib: kui n on graafi tippude arv, siis Floyd-Warshalli algoritm annab etapi n tulemuseks maatriksi, kus aij on lühima tee pikkus tipust i tippu j .
annaabi.ee 
