Алгоритм Краскала
Vložit
- čas přidán 6. 08. 2018
- Алгоритм Краскала для нахождения минимального остовного дерева в графе.
Следующий алгоритм - алгоритм Борувки для нахождения минимального остова. Затем я заканчиваю с остовными деревьями.
Вопросы, предложения, новые алгоритмы - пишите в комментариях.
6:24 мой любимый момент, ведь тут автор говорит 5-6 и 7-8. Включили видео на уроке информатики, знатно поржали. 10 класс, че сказать)
Автор, круто объясняешь!!! плиз продолжай делать видео про алгоритмы.
Нет 😡😡😡
Для интересующихся графами рекомендую свободно распространяемую электронную книгу «Графомания» (автор Деревенец О.В.). Даны решения задач с исходными текстами и контрольными примерами. Рассмотрены следующие темы:
Задачи на множествах:
• разбиение множества на подмножества;
• задача о наименьшем разбиении (ЗНР);
• задача о наименьшем покрытии (ЗНП).
Группа задач на достижимость:
• взаимная достижимость вершин;
• кратчайшие пути между вершинами;
• выделение сильно связанных компонент.
Группа задач на размещение:
• независимые вершины и клики;
• доминирующие множества;
• раскраски;
• центры;
• p-центры;
• p-медианы.
Остовные деревья
Группа задач о потоках:
• максимальный поток в сети;
• поток, ограниченный сверху и снизу;
• минимальная стоимость потока.
Паросочетания на взвешенных графах:
• паросочетание в двудольном графе;
• паросочетание в произвольном графе.
Цикл Эйлера и задача почтальона на взвешенных графах:
• на неориентированном графе;
• на орграфе.
Задачи Гамильтона и коммивояжёра на взвешенных графах:
• разомкнутая задача Гамильтона;
• замкнутая задача Гамильтона (контур);
• комбинирование методов для задач Гамильтона;
• замкнутая и разомкнутая задачи коммивояжёра.
а как доказать, что это будет минимальное по сумме оставное дерево из всех возможных построений? по процессу не очевидно... выбирали рандомно (хоть и из минимальных)
Подскажите, пожалуйста, для чего вообще применяется основное дерево? Что с ним делать после того как нашел?
Применений довольно много. Самое примитивное, к примеру, - построение сети дорог минимальной длины, которая бы соединяла несколько нселенных пунктов. Кроме того, деревья применяются и в доказательствах различных теорем, как, к примеру, соотношение между количеством вершин, ребер и граней многогранника. Это только два примера, но, встретившись с задачей, вы поймёте, если она решается с использованием остовного дерева.
@@user-yp6ze3dh5j спасибо большое за развернутый ответ)
Почему по вашему примеру дерево имеет 9 дуг при том, что у графа 9 вершин, если у остовного графа всегда на n-1 дуг меньше n
Вершин 10
В неорієнтованому графі немає дуг. Дугa - орієнтоване ребро
Дякую. Візьму до уваги.