"naabrusmaatriksist" - 1 õppematerjal

ITT0030 Diskreetne matemaatika II - eksamikonspekt

a). Naabrusmaatriksina- traditsiooniline graafi esitusviis, kus nii maatriksi ridadele kui ka veergudele vastavad graafi tipud ning 1'ga on tähistatud elemendid, kus kahe tipu 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