Минимальный остов

  Рет қаралды 43,571

Kirsanov2011

Kirsanov2011

Күн бұрын

Для отыскания остова наименьшего веса применяем алгоритм Краскала и алгоритм ближайшего соседа (Прима).
Показываем на примере, как вычислить число остовов графа. Выписываем матрицу Кирхгофа.

Пікірлер: 39
@arturwarios973
@arturwarios973 5 жыл бұрын
Чёткий мужик как поступил в универ, не отрываюсь от его канала. Очень доходчиво объяснят малораспространённую в инте информацию по дискретке
@torcher5023
@torcher5023 4 жыл бұрын
Где учишься?
@ДмитрийНормов-ю6ц
@ДмитрийНормов-ю6ц 2 жыл бұрын
@@torcher5023 уже на 4 курсе по ходу он..
@Kot_Kotovskey
@Kot_Kotovskey 3 жыл бұрын
Мужик,ты огонь,только благодаря тебе сдал зачёт по дискретной математике,огромное спасибо❤️
@Kirsanov2011
@Kirsanov2011 11 жыл бұрын
Есть еще и моя книга "Графы в Maple", Maple можно опустить, а задачи там есть. Можно скачать в интернете, я сам туда выложил на сайте "мируравнений" Андрея Полянина. Успехов!
@DonGrovello
@DonGrovello 11 жыл бұрын
Спасибо огромное за ваши лекции, очень помогли при изучении материала.
@Daloshka
@Daloshka Жыл бұрын
Спасибо, помогло разобраться с тем, что не понял на паре. Всё очень просто
@FladgameWordot999lvl
@FladgameWordot999lvl 2 жыл бұрын
Большое Спасибо!
@linoleum3m
@linoleum3m 7 жыл бұрын
просто шикарно объясняете! поняла с первого раза. очень помогли подготовиться к зачету) спасибо!)
@linoleum3m
@linoleum3m 7 жыл бұрын
сюда бы еще пример для ориентированного графа с разным весом между двумя вершинами)
@Kirsanov2011
@Kirsanov2011 11 жыл бұрын
Спасибо за высокую оценку и совет. Я не знал про cursera и udacity, это любопытно
@anthracites
@anthracites 7 жыл бұрын
Приятно слушать Ваши объяснения. Спасибо большое за помощь)
@ЕкатеринаПетрова-з5ж
@ЕкатеринаПетрова-з5ж 6 жыл бұрын
Большое спасибо! Все понятно и доступно.
@VendettaUkraina
@VendettaUkraina 10 жыл бұрын
Отлично. Спасибо. Наглядно лучше воспринимается, чем читать теорию в интернете
@kscherban
@kscherban 11 жыл бұрын
Очень доступно излагаете. Продолжайте в том же духе! Возможно, в скорости такие как вы откроют русский аналог coursera и udacity.
@94Ackar
@94Ackar 11 жыл бұрын
Коротко , ясно , доходчиво большое спасибо!
@МаратГафуров-ж4ы
@МаратГафуров-ж4ы 5 жыл бұрын
Лукас деду однозначно
@bahdanshyshkin7918
@bahdanshyshkin7918 6 жыл бұрын
Лучше, конечно, в долларах!
@googlehome322
@googlehome322 5 жыл бұрын
^_^ Сам угорел)
@alexeygabrusev709
@alexeygabrusev709 10 жыл бұрын
спасибо, очень компактно и по теме
@ПавелБелькевич-р6в
@ПавелБелькевич-р6в 11 жыл бұрын
Спасибо большое за ваши лекции,подписался.Хотелось бы еще лекций касательно теории графов
@ВестякАнатолий
@ВестякАнатолий 10 жыл бұрын
Спасибо!!!
@vladislav1ananiev
@vladislav1ananiev 4 жыл бұрын
Здравствуйте! Анатолий Васильевич)
@apaxuc13
@apaxuc13 11 жыл бұрын
спасибо!
@olgaivanova6569
@olgaivanova6569 10 жыл бұрын
Огромное спасибо за прекрасные лекции! Не подскажете ли какой-нибудь элегантный способ проверить, не образует ли добавляемое ребро цикл?
@sergeypankevich1827
@sergeypankevich1827 5 жыл бұрын
Olga Ivanova depth first search
@pruchay
@pruchay 9 жыл бұрын
А как быть если например два отрезка (или больше) с одинаковым весом? Вот у Вас на примере один отрезок с весом 14, а если таких будет два, как понять какой лучше выбрать первым? Спасибо.
@Kirsanov2011
@Kirsanov2011 9 жыл бұрын
pruchay Берите любой. Остов будет другой, а минимальный вес тот же. А бывает и остовы совпадают. Простой пример: возьмите граф с одинаковыми весами всех ребер. Получится множество остовов с одинаковым весом.
@pruchay
@pruchay 9 жыл бұрын
Kirsanov2011 Спасибо. Ваши видео очень мне помогли понять суть. Надеюсь сдам таки предмет)
@DonGrovello
@DonGrovello 11 жыл бұрын
Я никак не могу найти иллюстрацию алгоритмов Флойда - Уоршелла и Беллмана - Форда, на вашем канале тоже не нашел лекций на эту тему. Не подскажете где еще поискать?
@IXeRios
@IXeRios 8 жыл бұрын
ваш алгоритм, который вы обозвали "ближайший сосед" существует уже 86 лет и называет алгоритм Прима (был переоткрыт им в 1957)
@Kirsanov2011
@Kirsanov2011 8 жыл бұрын
Я его и не присваиваю себе. Это общепринятое название - из названия становится сразу понятен способ. А Прима ничего не говорит...
@IXeRios
@IXeRios 8 жыл бұрын
вот только за эти слова мы, студенты, по шапке от преподов получаем, т.к такого названия нету в литературе и они такого выражения не употребляют
@Kirsanov2011
@Kirsanov2011 8 жыл бұрын
В литературе есть. Мало, но есть. Могу привести источник. Но на всякий случай подправил видео в виде аннотации. Девиз преподавателя - "Не навреди" (как и врача).
@IXeRios
@IXeRios 8 жыл бұрын
спасибо за ваши видео!
@Kirsanov2011
@Kirsanov2011 11 жыл бұрын
Все дело в названиях. Я знаю алгоритм Уоршелла - это о транзитивном замыкании. См. в частн. "Курс лекций. Элементы дискретной математики" на моем сайте vuz.exponenta.ru в разделе Библиотека. Алг. Форда по ур-ям Беллмана см. в книге В.Н.Касьянов, В.А. Евстигнеев "Графы в программировании", bhv, 2003.- альтернатива Дейкстры.
@Kirsanov2011
@Kirsanov2011 11 жыл бұрын
что конкретно? Там уже много по теории графов... См. мой сайт vuz.exponenta.ru раздел ВИДЕО
@malakhov7145
@malakhov7145 4 жыл бұрын
Спасибо!
@evgenkazakov
@evgenkazakov 8 жыл бұрын
Спасибо!
Насыщение сети
17:17
Kirsanov2011
Рет қаралды 59 М.
Алгоритм Дейкстры
10:35
Kirsanov2011
Рет қаралды 150 М.
Men Vs Women Survive The Wilderness For $500,000
31:48
MrBeast
Рет қаралды 104 МЛН
Do you choose Inside Out 2 or The Amazing World of Gumball? 🤔
00:19
Профилактика лудомании
2:55
ALTAI TV
Рет қаралды 2
Графы. Деревья. Остов графа
10:49
Система кружков Фрактал
Рет қаралды 20 М.
Фундаментальные циклы и разрезы
19:13
Метод отжига
25:51
Kirsanov2011
Рет қаралды 18 М.
ВСЯ теория по графам для олимпиад
21:16
Дмитрий Белов. Олимпиадная математика в Школково
Рет қаралды 21 М.
Муравьиный алгоритм
37:01
Kirsanov2011
Рет қаралды 44 М.
Минимальное остовное дерево. Алгоритм Прима
16:13
Учиться - значит делать!
Рет қаралды 12 М.