Проверка, является ли v листом в MST

Question

У меня есть этот вопрос:

Учитывая неориентированный граф G = (V, E), V ∋ v и неотрицательные веса W найти, существует ли минимальное остовное дерево (MST), где v - лист и если есть, верните его.

Я думал о том, чтобы найти MST, используя алгоритм prim, и проверить, является ли v листом в нем. Если v не лист, я найду второй MST и проверим его. Проблема в том, что сложность времени будет слишком высокой. Я уверен, что есть другой способ решить эту проблему, но я не знаю как. Не могли бы вы дать мне понять, как подойти к этому вопросу?

Answer 1

Проблема с "сгенерировать все MST и проверить, является ли v листом в любом из них" в том, что число MST в графе может быть огромным : это может быть целым числом n ** (n-2), где n - количество узлов.

Лучше всего наблюдать, что все MST данного графа имеют одинаковый общий вес. Таким образом, более эффективный алгоритм может работать так:

• Примените стандартный алгоритм, чтобы найти MST G. Пусть total_weight будет его общим весом.
• Примените стандартный алгоритм, чтобы найти MST G - v, то есть график без узла v. Пусть mst_without_v будет этим MST, и пусть weight_without_v будет его общим весом.
• Если v имеет ребро веса total_weight - weight_without_v, то добавьте это ребро к mst_without_v и верните его. В противном случае, верните null.

Если алгоритм возвращает график, то это MST G, потому что он охватывает (G - v) + v = G, это дерево (потому что он был сформирован из дерево с добавленным одним листом), и он имеет правильный общий вес.

Если алгоритм возвращает null, то MST с G не существует, где v является листом. В противном случае удаление v из такого MST даст MST G - v с неправильным общим весом.