SHPORA.net :: PDA

[ Back ]

Graafi kujutamine



1. Joonis (huvipakkuv probleem selles valdkonnas - tasandilised graafid).

2. Kaarte loetelu (eeldades, et otstippude kohta käiv informatsioon on kaares olemas).

Sellise loetelu organiseerimiseks on palju võimalusi.

3. Külgnevusmaatriks (kaaslusmaatriks) jt. graafi ühest taastamist võimaldavad maatriksid.

4. Külgnevusstruktuur - tippude loetelu, milles iga tipuga on seotud sellest lähtuvate kaarte loetelu (iga kaare kohta on teada tipp, kuhu ta suubub).

Kauguste maatriks D=d[i, j] on |V|x|V| maatriks, milles d[i, j] on kaare (i, j) "pikkus" (kui kaar puudub, võib pikkuseks lugeda lõpmatuse).



Analoogiliselt võib kaartega siduda kaalud - tulemuseks on nn. kaalude maatriks (puuduva kaare kaal tavaliselt null).



Tipust v lähtuvate kaarte hulka tähistame:



Adj(v) = {e hulgast E | w kuulub hulka V: e=(v,w)}