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