Лекции 14. Основные понятия теории графов. Некоторые виды графов (4 часа)



Download 1,82 Mb.
bet20/29
Sana14.07.2022
Hajmi1,82 Mb.
#798900
TuriЛекции
1   ...   16   17   18   19   20   21   22   23   ...   29
Bog'liq
Теория графов

3. Алгоритм Крускала:
1) Выбрать в графе G ребро e минимального веса, не принадлежащее множеству E и такое, что его добавление в E не создает цикл в дереве T.
2) Добавить это ребро во множество ребер E.
3) Продолжить, пока имеются ребра, обладающие указанными свойствами.
Пример. Для данного взвешенного графа найти минимальное корневое остовное дерево, используя алгоритм Крускала. Определить высоту построенного дерева.



Алгоритм Крускала. Выбираем ребро с минимальным весом. Это ребро, ( , ) с весом, равным 4.
Пусть вершина будет корнем дерева. Далее выбираем ребра, инцидентные вершинам , и имеющие минимальный вес.
Это ребро ( , ) с весом 5. Затем к вершине присоединяем ребро ( , ) с весом 7.
Далее, добавляем ребро ( , ) с весом 7 и ребро ( , ) с весом 6.
Минимальный вес построенного дерева равен: min(T)=4+5+7+7+6=29.



4. Алгоритм Прима
Всегда имеется дерево, к которому ребра добавляют до тех пор, пока не получится остовное дерево.
Используя алгоритм Прима, сначала выбираем вершину v0 графа G, а затем выбираем ребро с наименьшим весом e1 = {v0 ,v1}, инцидентное к вершине v0 и формируем дерево Т1.
Следующим выбираем ребро с наименьшим весом е2 такое, что одна вершина ребра принадлежит дереву T1, а вторая — нет, и добавляем его в дерево, после чего получаем дерево T2 с двумя ребрами.
Сформировав дерево Тk формируем дерево Тk+1, выбирая ребро с минимальным весом ek+1 такое, что одна его вершина принадлежит дереву Тk, а другая — нет, и добавляем это ребро в дерево.
Продолжаем процесс до тех пор, пока дерево не будет содержать все вершины графа G.
1) Выбрать вершину v0 графа G и ребро с наименьшим весом e1, для которого v0 – одна из вершин, и сформировать дерево T1.
2) Для заданного дерева Tk с ребрами e1, e2, e3, …, ek, если имеется вершина, не принадлежащая Tk, выбрать ребро с наименьшим весом, смежное с ребром дерева Tk и имеющее вершину вне дерева Tk. Добавить в дерево Tk, формируя дерево Tk+1.
3) Продолжить, пока имеются вершины графа G, не принадлежащие дереву.

Построение минимального остовного дерева можно проводить двумя способами:


1) остов графа строится непосредственно на самом графе, выделяя ребра утолщенной линией, которые входят в остовное дерево;
2) строится отдельно корневое дерево, которое будет минимальным остовным деревом. Второй случай используется, если требуется определить высоту построенного дерева.
Пример. Рассмотрим граф.

Начав с вершины а, первым выбираем ребро {а, е}, поскольку оно имеет минимальный вес.
Т. о. дерево T1 состоит из ребра {а, е}.
Теперь выбираем ребро {e,d}, так как это ребро с минимальным весом из тех, что имеют только одну вершину в дереве T1.
Получаем дерево Т2.
Д алее выбираем ребро {d, b}, поскольку это ребро с минимальным весом из тех, что имеют только одну вершину в Т2. Получаем Т3.
Теперь, так как имеется два ребра с одинаковым весом и одной вершиной в Т3, имеем выбор.
П редположим, выбрано ребро {d,c}, поэтому дерево Т4 имеет следующий вид.
Следующим выбираем ребро {е, f}. Это ребро имеет минимальный вес из тех, что имеют только одну вершину в дереве Т4; отсюда Т5
Наконец, выбираем ребро {f,g}. Поскольку это ребро минимального веса из тех, что имеют одну вершину в Т4, а вершина g — последняя из оставшихся вершин, имеем дерево Т6, которое является искомым остовным деревом.

ВЕС МОД 2+2+1+4=9

Download 1,82 Mb.

Do'stlaringiz bilan baham:
1   ...   16   17   18   19   20   21   22   23   ...   29




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish