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