Если граф G имеет различные реберные затраты> 0 (т.е. нет двух одинаковых реберных затрат), является ли каждое дерево с минимальным узким местом G также деревом с минимальным охватом?

Question

Мой первоначальный ответ - да, с доказательством от противного.

"Предположим, что существует дерево с минимальным узким местом T1 в G и минимальное остовное дерево T2 в G, такое, что T1 не равен T2. Это означает, что общий вес ребер T1 больше, чем вес ребер T2. Поскольку все затраты ребер различны, это означает, что значение ребра узкого места T1 должно быть больше, чем значение T2. Однако, если это правда, это означает, что узкое место T2 меньше, чем у T1, то есть T1 не является MBST, что является противоречием. QED.

Я знаю, что если пограничные затраты не различаются, то ответом будет «нет», MBST не обязательно является MST, но если пограничные затраты Я считаю, что все меняется.

Answer 1

Вы делаете логический скачок, заключая: " Поскольку все пограничные затраты различны, это означает, что значение пограничного узкого места T1 должно быть больше, чем значение T2 " из " Это означает, что общий вес ребер T1 больше, чем вес ребер T2."

Общий вес представляет собой сумму. Одна сумма может быть больше другой, даже если у обоих одинаковый наибольший срок. Независимо от того, различаются ли числа, не имеет значения.

Ищите небольшой контрпример с 4 вершинами и 4 ребрами.