Вот акциз:
Либо доказать следующее, либо дать контрпример:
(a) Является ли путь между парой вершин в минимальном остовном дереве неориентированного графа обязательно самый короткий (минимальный вес) путь?
(b) Предположим, что минимальное связующее дерево графа уникально. Является путь между парой вершин в минимальном остовном дереве неориентированный граф обязательно самый короткий (минимальный вес) путь?
Мой ответ
(а)
Нет, например, для графа 0, 1, 2, 0-1 равно 4, 1-2 равно 2, 2-0 равно 5, тогда 0-2s истинный самый короткий путь равен 5, но mst равен 0- 1-2, в mst, 0-2 равно 6
(б)
Моя проблема входит в это (б).
Я не понимаю, как whether the MST is unique может повлиять на кратчайший путь.
Во-первых, я понимаю, что когда веса ребер не отличаются друг от друга, несколько MST могут существовать одновременно, верно?
Во-вторых, даже если MST уникален, ответ (a) выше применяется для (b), правильно?
Относительно (а), я согласен.
В отношении (b) для некоторых графиков могут быть более минимальные связующие деревья с одинаковым весом. Рассмотрим окружность C3 с вершинами a, b, c; веса a- > b = 1, b- > c = 2, a- > c = 2. Этот граф имеет два MST, {a-b-c} и {c-a-b}.
Тем не менее, ваш контрпример все еще сохраняется, потому что MST там уникален.
Итак, давайте взглянем на очень простой график:
(A)---2----(B)----2---(C)
\ /
---------3----------
Минимальное связующее дерево для этого графа состоит из двух ребер A-B и B-C. Ни один другой набор ребер не образует минимальное остовное дерево.
Но, конечно, кратчайший путь от A до C равен A-C, который не существует в MST.
ИЗМЕНИТЬ
Таким образом, чтобы ответить на часть (b), ответ отрицательный, потому что существует более короткий путь, который не существует в MST.
Разве MST не связан с запуском node?
Затем он пытается получить кратчайший путь от начала MST node. Поэтому да, кратчайший путь задается MST, начиная с A!