Полная версия этого вопроса цитируется ниже:
Пусть G - связный граф с n вершинами, m ребрами с различными весами ребер. Пусть T - дерево G с n вершинами и n-1 ребром (то есть остовное дерево), и определим ребро узкого места T как ребро T с наименьшим весом. Дерево максимального узкого места является остовным деревом группы G, если не существует остовного дерева с большим краем узкого места. Докажите или приведите контрпример для следующего утверждения:
Каждое max-остовное дерево группы G является максимальным узким местом группы G
Я думаю, что, поскольку граф имеет уникальные веса ребер, каждое остовное дерево группы G также уникально. Тогда существует только одно максимальное остовное дерево группы G, и если я смогу доказать, что это дерево также является деревом максимального бутылочного горлышка, то это подтвердит истинность этого утверждения, но только если оно истинно для всех графов с уникальными весами ребер. .
Я попытался найти контрпримеры, чтобы доказать это неверно, но пока похоже, что каждый граф, который я рисую с уникальными весами ребер, заканчивается, так что максимальное остовное дерево также является максимальным деревом узких мест. Я думаю, что могу использовать это, чтобы доказать, что это утверждение истинно, но я не знаю, как его сформулировать.
