шпаргалка

Graafi kujutamine, graafiga seotud maatriksid, tehted graafidega.

[ Назад ]



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)}



КАТЕГОРИИ:

Network | английский | архитектура эвм | астрономия | аудит | биология | вычислительная математика | география | Гражданское право | демография | дискретная математика | законодательство | история | квантовая физика | компиляторы | КСЕ - Концепция современного естествознания | культурология | линейная алгебра | литература | математическая статистика | математический анализ | Международный стандарт финансовой отчетности МСФО | менеджмент | метрология | механика | немецкий | неорганическая химия | ОБЖ | общая физика | операционные системы | оптимизация в сапр | органическая химия | педагогика | политология | правоведение | прочие дисциплины | психология (методы) | радиоэлектроника | религия | русский | сертификация | сопромат | социология | теория вероятностей | управление в технических системах | физкультура | философия | фотография | французский | школьная математика | экология | экономика | экономика (словарь) | язык Assembler | язык Basic, VB | язык Pascal | язык Си, Си++ |