Минимальное связующее дерево с узким местом взвешенного графа G является остовным деревом G, которое минимизирует максимальный вес любого ребра в остовном дереве. MBST не обязательно является MST (минимальное остовное дерево).
Просьба привести пример, где эти утверждения имеют смысл.
Посмотрите пример MST в Википедии для справки:
Узкое место в остовном дереве - это край максимального веса в этом дереве. В остовном дереве может быть несколько узких мест (все одинакового веса). В Wikipedia MST есть два узких места с весом 8.
Теперь возьмем минимальное связующее дерево данного графика (может быть несколько MST, все с одинаковым общим весом кромки, конечно) и назовем максимальный вес B. В нашем примере B = 8.
Любое остовное дерево, которое также имеет узкое место B = 8, является MBST. Но это может быть не MST (потому что общий вес края больше, чем это возможно).
Итак, возьмите Wikipedia MST и измените его (добавьте/удалите некоторые ребра), чтобы
Например, измените только поддерево "слева" из Miki Википедии (состоящее из весов {2, 2, 3}) до {2, 3, 6}, тем самым увеличив общий вес кромки на 4 без изменения узкое место 8. Бинго, вы создали MBST, который не является MST.
Прежде чем ответить на ваш вопрос, позвольте мне определить некоторые термины, которые используются здесь...
1) Spanning Tree: Spanning tree данного графа - это дерево, которое покрывает все вершины в этом графе.
2) Минимальное остовное дерево (MST): MST данного графа является связующим деревом, длина которого минимальна среди всех возможных связующих деревьев этого графа. Более четко, для данного графика, перечислите все возможные связующие деревья (которые могут быть очень большими) и выберите ту, чья сумма весов ребер минимальна.
3) Минимальное связующее дерево (MBST): MBST данного графа - это остовное дерево, максимальный размер края которого минимален среди всех возможных остовных деревьев. Более четко, для данного графика, перечислите все возможные связующие деревья и максимальный вес края для каждого из остовных деревьев. Среди них выбирается остовное дерево, максимальный вес кромки которого минимален.
Теперь давайте посмотрим на следующее изображение с четырьмя графами node...
График-A - это заданный исходный граф. Если я перечислю все возможные связующие деревья для этого графа и выберем ту, чья сумма весов ребер минимальна, тогда я получу график-B. Поэтому Graph-B - это минимальное связующее дерево (MST). Обратите внимание, что его общий вес равен 1 + 2 + 3 = 6.
Теперь, если я выбираю остовное дерево, максимальный вес края которого минимален (например, MBST), тогда я могу в итоге получить либо график-B (или) Graph-C. Обратите внимание, что обе эти связующие деревья имеют максимальный вес края 3, что является минимальным среди всех возможных связующих деревьев.
Из графиков-B и Graph-C ясно, что даже если Graph-C является MBST, это не MST. Поскольку его общий вес равен 1 + 3 + 3 = 7, что больше, чем общий вес MST, нарисованный на графике-B (т.е. 6).
Таким образом, MBST не обязательно является MST данного графика. Но MST должен быть MBST.
