План лекции
Date: 2014-03-11; view: 452.
Таблиця.
Приклад 2.
Теорема 3.
Алгоритм Краскала утворює мінімальне каркасне дерево.
На (мал. 3) зображений граф, ребра якого пронумеровано за зростанням ваг. Мінімальний каркас виділено потовщеними лініями. Процес добору ребер наведено у таблиці. Вибрано n-1= 7-1 = 6 ребер, робота закінчена. Після вибору ребра е11 на останньому кроці отримали 
.
Каркас утворюють ребра е1, е2, е3, е5, е8, е11.
| Ребро | Розбиття множини вершин | Відбір ребра у мінімальний каркас |
| 
| 
|
| 
| 
|
| 
| 
|
| 
| - |
|
| 
|
| 
| - |
|
| - |
|
| 
|
| 
| - |
|
| - |
|
| 
|
|
Алгоритм Краскала належить до жадібних алгоритмів.
Запитання для самоперевірки.
1. Що таке каркас?
2. Як знайти цикломатичне число графа?
3. Як виглядає формула Кірхгофа?
4. Яка суть алгоритму Краскала?
Література
1. (Б1), с.682-685,
2. (Б8), с.248-251.
- Цель работ. Актуальность. Классификация объектов.
- Насаждения на террасах и земляных насыпях.
- Природные компоненты на террасах над транспортными и инженерными сооружениями.
- Природные компоненты в структуре зданий и сооружений.
- Природные компоненты: озеленение интерьера, зимние сады, оранжереи, дизайн крытых пешеходных галерей, дизайн подземных пространств.
- Озеленение крыш: экстенсивное и интенсивное озеленение. Сады на крышах.
| <== previous lecture | | | next lecture ==> |
| И коммуникативная эффективность рекламы | | | Поняття системи |