Для отыскания остова наименьшего веса применяем алгоритм Краскала и алгоритм ближайшего соседа (Прима). Показываем на примере, как вычислить число остовов графа. Выписываем матрицу Кирхгофа.
Есть еще и моя книга "Графы в Maple", Maple можно опустить, а задачи там есть. Можно скачать в интернете, я сам туда выложил на сайте "мируравнений" Андрея Полянина. Успехов!
А как быть если например два отрезка (или больше) с одинаковым весом? Вот у Вас на примере один отрезок с весом 14, а если таких будет два, как понять какой лучше выбрать первым? Спасибо.
pruchay Берите любой. Остов будет другой, а минимальный вес тот же. А бывает и остовы совпадают. Простой пример: возьмите граф с одинаковыми весами всех ребер. Получится множество остовов с одинаковым весом.
Все дело в названиях. Я знаю алгоритм Уоршелла - это о транзитивном замыкании. См. в частн. "Курс лекций. Элементы дискретной математики" на моем сайте vuz.exponenta.ru в разделе Библиотека. Алг. Форда по ур-ям Беллмана см. в книге В.Н.Касьянов, В.А. Евстигнеев "Графы в программировании", bhv, 2003.- альтернатива Дейкстры.
Я никак не могу найти иллюстрацию алгоритмов Флойда - Уоршелла и Беллмана - Форда, на вашем канале тоже не нашел лекций на эту тему. Не подскажете где еще поискать?
В литературе есть. Мало, но есть. Могу привести источник. Но на всякий случай подправил видео в виде аннотации. Девиз преподавателя - "Не навреди" (как и врача).
Чёткий мужик как поступил в универ, не отрываюсь от его канала. Очень доходчиво объяснят малораспространённую в инте информацию по дискретке
Где учишься?
@@torcher5023 уже на 4 курсе по ходу он..
Мужик,ты огонь,только благодаря тебе сдал зачёт по дискретной математике,огромное спасибо❤️
Есть еще и моя книга "Графы в Maple", Maple можно опустить, а задачи там есть. Можно скачать в интернете, я сам туда выложил на сайте "мируравнений" Андрея Полянина. Успехов!
Приятно слушать Ваши объяснения. Спасибо большое за помощь)
Спасибо огромное за ваши лекции, очень помогли при изучении материала.
Спасибо, помогло разобраться с тем, что не понял на паре. Всё очень просто
Спасибо за высокую оценку и совет. Я не знал про cursera и udacity, это любопытно
Большое спасибо! Все понятно и доступно.
просто шикарно объясняете! поняла с первого раза. очень помогли подготовиться к зачету) спасибо!)
сюда бы еще пример для ориентированного графа с разным весом между двумя вершинами)
Очень доступно излагаете. Продолжайте в том же духе!
Возможно, в скорости такие как вы откроют русский аналог coursera и udacity.
Отлично. Спасибо. Наглядно лучше воспринимается, чем читать теорию в интернете
Коротко , ясно , доходчиво
большое спасибо!
Спасибо большое за ваши лекции,подписался.Хотелось бы еще лекций касательно теории графов
Большое Спасибо!
спасибо, очень компактно и по теме
Лукас деду однозначно
Лучше, конечно, в долларах!
^_^ Сам угорел)
спасибо!
Спасибо!
Спасибо!!!
Здравствуйте! Анатолий Васильевич)
Огромное спасибо за прекрасные лекции! Не подскажете ли какой-нибудь элегантный способ проверить, не образует ли добавляемое ребро цикл?
Olga Ivanova depth first search
А как быть если например два отрезка (или больше) с одинаковым весом? Вот у Вас на примере один отрезок с весом 14, а если таких будет два, как понять какой лучше выбрать первым? Спасибо.
pruchay Берите любой. Остов будет другой, а минимальный вес тот же. А бывает и остовы совпадают. Простой пример: возьмите граф с одинаковыми весами всех ребер. Получится множество остовов с одинаковым весом.
Kirsanov2011 Спасибо. Ваши видео очень мне помогли понять суть. Надеюсь сдам таки предмет)
Все дело в названиях. Я знаю алгоритм Уоршелла - это о транзитивном замыкании. См. в частн. "Курс лекций. Элементы дискретной математики" на моем сайте vuz.exponenta.ru в разделе Библиотека. Алг. Форда по ур-ям Беллмана см. в книге В.Н.Касьянов, В.А. Евстигнеев "Графы в программировании", bhv, 2003.- альтернатива Дейкстры.
Я никак не могу найти иллюстрацию алгоритмов Флойда - Уоршелла и Беллмана - Форда, на вашем канале тоже не нашел лекций на эту тему. Не подскажете где еще поискать?
ваш алгоритм, который вы обозвали "ближайший сосед" существует уже 86 лет и называет алгоритм Прима (был переоткрыт им в 1957)
Я его и не присваиваю себе. Это общепринятое название - из названия становится сразу понятен способ. А Прима ничего не говорит...
вот только за эти слова мы, студенты, по шапке от преподов получаем, т.к такого названия нету в литературе и они такого выражения не употребляют
В литературе есть. Мало, но есть. Могу привести источник. Но на всякий случай подправил видео в виде аннотации. Девиз преподавателя - "Не навреди" (как и врача).
спасибо за ваши видео!
что конкретно? Там уже много по теории графов... См. мой сайт vuz.exponenta.ru раздел ВИДЕО
Спасибо!