Алгоритм Краскала

Алгоритм Краскала для нахождения минимального остовного дерева в графе.
Следующий алгоритм - алгоритм Борувки для нахождения минимального остова. Затем я заканчиваю с остовными деревьями.
Вопросы, предложения, новые алгоритмы - пишите в комментариях.

[@osnovapubg-he2hg]

молодец, все по факту рассказал, спасибо. лайк))

[@lieze976]

6:24 мой любимый момент, ведь тут автор говорит 5-6 и 7-8. Включили видео на уроке информатики, знатно поржали. 10 класс, че сказать)

[@walcermelodia]

Автор, круто объясняешь!!! плиз продолжай делать видео про алгоритмы.

[@КаналЭйса-ь8в]

Нет 😡😡😡

[@olegderevenets8943]

Для интересующихся графами рекомендую свободно распространяемую электронную книгу «Графомания» (автор Деревенец О.В.). Даны решения задач с исходными текстами и контрольными примерами. Рассмотрены следующие темы: Задачи на множествах: • разбиение множества на подмножества; • задача о наименьшем разбиении (ЗНР); • задача о наименьшем покрытии (ЗНП). Группа задач на достижимость: • взаимная достижимость вершин; • кратчайшие пути между вершинами; • выделение сильно связанных компонент. Группа задач на размещение: • независимые вершины и клики; • доминирующие множества; • раскраски; • центры; • p-центры; • p-медианы. Остовные деревья Группа задач о потоках: • максимальный поток в сети; • поток, ограниченный сверху и снизу; • минимальная стоимость потока. Паросочетания на взвешенных графах: • паросочетание в двудольном графе; • паросочетание в произвольном графе. Цикл Эйлера и задача почтальона на взвешенных графах: • на неориентированном графе; • на орграфе. Задачи Гамильтона и коммивояжёра на взвешенных графах: • разомкнутая задача Гамильтона; • замкнутая задача Гамильтона (контур); • комбинирование методов для задач Гамильтона; • замкнутая и разомкнутая задачи коммивояжёра.

[@egorrichmining1069]

а как доказать, что это будет минимальное по сумме оставное дерево из всех возможных построений? по процессу не очевидно... выбирали рандомно (хоть и из минимальных)

[@Deers67]

Подскажите, пожалуйста, для чего вообще применяется основное дерево? Что с ним делать после того как нашел?

[@РусланДиниц]

Применений довольно много. Самое примитивное, к примеру, - построение сети дорог минимальной длины, которая бы соединяла несколько нселенных пунктов. Кроме того, деревья применяются и в доказательствах различных теорем, как, к примеру, соотношение между количеством вершин, ребер и граней многогранника. Это только два примера, но, встретившись с задачей, вы поймёте, если она решается с использованием остовного дерева.

[@Deers67]

@@РусланДиниц спасибо большое за развернутый ответ)

[@oneguiry]

Почему по вашему примеру дерево имеет 9 дуг при том, что у графа 9 вершин, если у остовного графа всегда на n-1 дуг меньше n

[@РусланДиниц]

Вершин 10

[@bbmbyte]

В неорієнтованому графі немає дуг. Дугa - орієнтоване ребро

[@РусланДиниц]

Дякую. Візьму до уваги.

[@МихаилСтепанов-л3х]

Автор старался, но делал это исключительно нудно исключительно нудным голосом. Денис, учись говорить по нормальному. Курсы актерского мастерства послушай или как политиков говорить учат.

[@hulkdiamant]

Здесь не согласен, нужное ≠ спокойное. Он довольно спокойно объяснил тему и очень доходчиво. Я бы дал тебе послушать своего лектора по дискретной математики, для понимания что такое правда нудное и непонятное объяснение, а автору респект за объяснение сложного алгоритма за 10 минут