Для отыскания остова наименьшего веса применяем алгоритм Краскала и алгоритм ближайшего соседа (Прима). Показываем на примере, как вычислить число остовов графа. Выписываем матрицу Кирхгофа.
Есть еще и моя книга "Графы в Maple", Maple можно опустить, а задачи там есть. Можно скачать в интернете, я сам туда выложил на сайте "мируравнений" Андрея Полянина. Успехов!
Я никак не могу найти иллюстрацию алгоритмов Флойда - Уоршелла и Беллмана - Форда, на вашем канале тоже не нашел лекций на эту тему. Не подскажете где еще поискать?
А как быть если например два отрезка (или больше) с одинаковым весом? Вот у Вас на примере один отрезок с весом 14, а если таких будет два, как понять какой лучше выбрать первым? Спасибо.
pruchay Берите любой. Остов будет другой, а минимальный вес тот же. А бывает и остовы совпадают. Простой пример: возьмите граф с одинаковыми весами всех ребер. Получится множество остовов с одинаковым весом.
Все дело в названиях. Я знаю алгоритм Уоршелла - это о транзитивном замыкании. См. в частн. "Курс лекций. Элементы дискретной математики" на моем сайте vuz.exponenta.ru в разделе Библиотека. Алг. Форда по ур-ям Беллмана см. в книге В.Н.Касьянов, В.А. Евстигнеев "Графы в программировании", bhv, 2003.- альтернатива Дейкстры.
В литературе есть. Мало, но есть. Могу привести источник. Но на всякий случай подправил видео в виде аннотации. Девиз преподавателя - "Не навреди" (как и врача).
