"arvutustehnilistel" - 1 õppematerjal

ITT0030 Diskreetne matemaatika II - eksamikonspekt

hilisematel sammudel tuleb seetõttu võibolla teha ebasoodsaid otsuseid. [35]. Märgendatud puud. Puude esitamine arvuti mälus. Märgendatud puu korral on igale puu tipule omistatud konkreetne naturaalarvuline tähis hulgast {1,2,...n}. Reaalsetes rakendustes tegeldaksegi rohkem märgendatud puudega (neid puudutav teooria on seetõttu ka mahukam), märgendamata puid uuritakse suures osas vaid matemaatilistel ning arvutustehnilistel kaalutlustel. Märgendatud puude esitusviisid arvutimälus: 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