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

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

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

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

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

Пусть будет такой пример: 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

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

1 ---2--- 3 \ | \ | \ | \ | \ | \ | \ | 4---5

Веса ребер: 1 ---2--- 3: 2, 3, 4 \ |: 5 \ |: 6 \ |: 7 \ |: 8 \ |: 9 \ |: 10 \ |: 11 4---5: 12, 13

При применении алгоритма Прима, минимальное остовное дерево будет состоять из ребер (1, 2), (2, 3), (3, 5). Суммарный вес ребер равен 9.

При применении алгоритма Краскала, минимальное остовное дерево будет состоять из ребер (1, 2), (2, 3), (3, 4). Суммарный вес ребер равен 9.

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

ссылка

отвечен 4 Янв 19:04

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

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

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

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

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

отмечен:

×2,138
×1,230
×709
×304

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

показан
1401 раз

обновлен
4 Янв 19:04

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

по почте:

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

по RSS:

Ответы

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

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