|
Привести пример взвешенного графа на 5 вершинах , на котором алгоритмы Прима и Краскала дают одинаковый результат только на последнем шаге задан 25 Дек '16 22:45 
explicit |
|
Пусть будет такой пример: 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 
falcao |
|
Приведу пример взвешенного графа на 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 
whoami |
Я в целом понимаю, что надо получить, но вообще-то задачи такого рода следует формулировать точнее, сопровождая разъяснениями. Хотя речь идёт об алгоритмах, то есть об однозначных процедурах, на деле они таковыми не являются, потому что допускают произвол в выборе начальной вершины или рёбер одинакового веса. Конечно, на техническом уровне всегда добиваются детерминированности, но саму осуществлять это можно по-разному.
Предлагаю такое толкование: надо придумать граф и два алгоритма, один из которых можно считать алгоритмом П., а второй алгоритмом К. Промежуточные суммы весов всегда разные.