Решите, существует ли MST, который содержит несколько ребер из двух различных наборов ребер.

Пусть G = (V, E) — взвешенный, связный и неориентированный граф. Пусть T1 и T2 будут двумя разными MST. Предположим, что мы можем написать E = (A1 U B U A2) таким образом, что:
B является пересечением ребер T1 и T2, и
A1 = T1 - B
A2 = T2 - B

Предполагая, что каждая MST T в G содержит все ребра B, найдите алгоритм, определяющий, существует ли MST T, содержащая хотя бы одно ребро в A1 и хотя бы одно ребро в A2.

Редактировать: я уронил часть, которая была здесь. Я думаю, что это приносит больше вреда, чем пользы.


algorithm graph-algorithm minimum-spanning-tree kruskals-algorithm
person Robert777    schedule 27.04.2013    source источник
comment
Либо черный ящик — отвлекающий маневр, либо автору вопроса следует обновить свои знания о матроиды.   -  person David Eisenstat    schedule 27.04.2013
comment
Привет Дэвид. Прежде всего, мы не узнали, что такое матроид, поэтому я не понимаю, что вы имеете в виду. Я сказал, что можно использовать алгоритм, описанный в последнем абзаце, но не обязательно.   -  person Robert777    schedule 27.04.2013

Ответы (1)


arrow_upward
1
arrow_downward

вы должны отсортировать свой край так, чтобы красный край предпочитал синий край для выбора. Затем вы можете использовать любой алгоритм MST, такой же, как Алгоритм Прима:

Если граф пуст, то мы немедленно закончим. Таким образом, мы предполагаем обратное. Алгоритм начинается с дерева, состоящего из одной вершины, и непрерывно увеличивает его размер на одно ребро за раз, пока не охватит все вершины. Вход: непустой связный взвешенный граф с вершинами V и ребрами E (веса могут быть отрицательными). Инициализировать: Vnew = {x}, где x — произвольный узел (начальная точка) из V, Enew = {} Повторять до тех пор, пока Vnew = V: выбрать ребро {u, v} с минимальным весом, такое что u находится в Vnew и v (если есть несколько ребер с одинаковым весом, любое из них может быть выбрано) Добавить v к Vnew и {u, v} к Enew Вывод: Vnew и Enew описывают минимальное остовное дерево

person amin k    schedule 27.04.2013
comment
Спасибо за ответ. Прошу прощения, но мне кажется, что я должен был сформулировать свой вопрос по-другому. Нам нужно найти алгоритм, который решает, существует ли MST T, который содержит хотя бы одно ребро в A1 и хотя бы одно ребро в A2. - person Robert777; 28.04.2013
comment
поэтому отсортируйте a1 и a2, затем выберите первое ребро в a1 и a2. Теперь выполните алгоритм для другого ребра. - person amin k; 28.04.2013
comment
Откуда вы знаете, что если есть другой MST, вы его найдете? - person Robert777; 28.04.2013
comment
вы хотите найти все mst в вашем графике? - person amin k; 28.04.2013
comment
Нет. Нам дается 2 разных MST: T1 и T2. Нам нужно определить, существует ли хотя бы одно MST, содержащее ребра из A1 и ребра из A2 (и, очевидно, это означает, что MST отличается от T1 и T2). - person Robert777; 28.04.2013