Привести пример взвешенного графа на 5 вершинах , на котором алгоритмы Прима и Краскала дают одинаковый результат только на последнем шаге

задан 25 Дек '16 22:45

Я в целом понимаю, что надо получить, но вообще-то задачи такого рода следует формулировать точнее, сопровождая разъяснениями. Хотя речь идёт об алгоритмах, то есть об однозначных процедурах, на деле они таковыми не являются, потому что допускают произвол в выборе начальной вершины или рёбер одинакового веса. Конечно, на техническом уровне всегда добиваются детерминированности, но саму осуществлять это можно по-разному.

Предлагаю такое толкование: надо придумать граф и два алгоритма, один из которых можно считать алгоритмом П., а второй алгоритмом К. Промежуточные суммы весов всегда разные.

(25 Дек '16 23:36) falcao
10|600 символов нужно символов осталось
1

Пусть будет такой пример: AB=3, BC=4, CD=6, DE=9, EA=12, AC=5, CE=10, EB=11, BD=7, DA=8 (рекомендуется нарисовать). Пусть алгоритм Прима начинает с вершины E. Тогда он выбирает ребро ED=9. Далее присоединится DC=6, потом CB=4, и на последнем шаге AB=3. Это даёт сумму 9+6+4+3=22.

Алгоритм Краскала выберет на первом шаге AB=3, Затем BC=4. Далее он не выберет AC=5, так как это даёт цикл, и ребро допустимое минимальной стоимости будет CD=6. Последним будет DE=9, так как DA и DB выбирать нельзя. Здесь сумма та же: 3+4+6+9=22, и даже числа те же, но идут они в обратном порядке, поэтому промежуточные суммы весов для второго алгоритма всегда будут меньше.

ссылка

отвечен 25 Дек '16 23:44

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,040
×591
×379
×152

задан
25 Дек '16 22:45

показан
446 раз

обновлен
25 Дек '16 23:44

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru