vahel leidub serv. Ebaefektiivne ning mälu raiskav esitusviis. Vajadus mälus järele: b). Servade loendina- servade loendi puhul on puu esitatud kaheelemendiliste järjenditena, kus järjendi komponentideks on puu tipud, mida serv ühendab. Tunduvalt efektiivsem esitusviis naabrusmaatriksist. Vajadus mälu järele: 2n. c). Prüferi koodina- Prüferi koodi moodustamine koosneb laias laastus vähima märgendiga lehe leidmisest ja selekteerimisest, tema naabertipu ülesmärkimisest, ning antud tipu kustutamisest. Kõige efektiivsem märgendatud puude esitusviis arvuti mälus. Vajadus mälu järele: (n-1). [36]. Prüferi kood. Märgendatud puude loendamine. Cayley teoreem. Prüferi kood on kindlat märgendatud puud esitav arvujada pikkusega n - 2, kus n on antud puu tippude arv. Iga puu prüferi kood on unikaalne. Puu esitamine Prüferi koodina- a). Esmalt teen kontrolli mõttes kindlaks puu Prüferi koodi pikkuse (n-2).
saadakse igast koodist puu. **Cayley teoreem. [2] Märgendatud puu o Puu, mille tipud on märgendatud arvudega 1, …, n. Märgendatud puu Prüferi kood o Prüferi koodi saame teatud viisil järjestatud servade loendist. o Koostame kahe reaga tabeli, kus igal sammul 1) leiame puus vähima märgendiga lehe, 2) kirjutame lehe märgendi yi ülemisse ritta ja tema naabertipu märgendi xi tema alla alumisse ritta, 3) kustutame puust selle lehe ja temaga intsidentse serva. o Kordame seda seni, kuni kõik servad on kustutatud (n - 1 korda). Saame tabeli, kus iga veerg vastab ühele eemaldatud servale. o Alati kehtib xn-1 = n, sest suurima märgendiga tipp jääb alati viimaseks. o Prüferi koodi moodustavad tabeli alumise rea n - 2 arvu x1, x2, …, xn-2
ja sellele lisaks dd(y) (v-st y-ni). See tähendab, et naabrid annavad informatsiooni, kuidas nendest kuhugi pääseb ja mina panen juurde selle, kuidas naabrini pääseb ja selle põhjal tehakse marsruutimisotsus. dv(z)= 2+1+2=5; dx(z)=1+2=3; ddz=1+2=3 du(z) = min { c(u,v) + dv(z), c(u,x) + dx(z), c(u,w) + dw(z) } = min {2 + 5, 1 + 3, 5 + 3} = 4 Näeme, et parim tee on uxyz, mille väärtus on 4. Bellman-Fordi näide: Teeme marsruutimistabeli tipu u kohta. Me otsime tipu u naabertipu v, mille vahel ei ole rohkem võrgusõlmi, vaid on ainult kanal. Nende kohta me teadme kanali väärtust. Kui tippude vahel on rohkem sõlmi kui üks, siis nende jaoks me ütleme, et see tee väärtus on lõpmatult suur. Tuleb otsida välja minimaalne tee. Naabrid annav oma informatsiooni, mina panen juurde teepikkuse naabriteni ja leian minimaalse. Algoritm töötab nii, et kui toimub lokaalse kanali väärtuse muutus või tuleb
annaabi.ee 
