Кратчайший путь остов с 1 взвешенными дугами против MST

Question

Я обучающиеся о графах и их алгоритмы, и я заметил, вопрос, который я не знаю, чтобы точно доказать:

Если мы связный неориентированный граф, G = (V, E) и каждые край имеет вес = 1, верно ли, что каждое связующее дерево, построенное из кратчайших путей от корня, является минимальным остовным деревом?

Я провел несколько примеров в http://visualgo.net/sssp.html и мне кажется, что ответ на этот вопрос верен, но кто-то может показать мне, как я могу это доказать? и еще один вопрос, который перешел мне на ум, верно и другое направление?

Answer 1

TLDR: Не обязательно

Рассмотрим треугольник график с единичными весами - она ​​имеет три вершины х, у, г, и все три ребра {х, у}, {х, г} , {y, z} есть единичный вес.

Самый короткий путь между любыми двумя вершинами - это прямой путь. Согласен?

Однако, чтобы удовлетворять условию MST на графике, вам необходимо собрать набор из двух ребер, соединяющих 3 вершины. Скажем {x, y}, {y, z} например. Это не кратчайший путь между любой парой вершин.

Следовательно, ваше предложение ложно :)

Answer 2

Каждое дерево имеет ровно n - 1 ребра. Так как все веса равны 1, то каждое остовное дерево G имеет общий вес n - 1. Это справедливо и для минимального остовного дерева. Так что да.