Существует ли минимальное остовное дерево, в котором нет минимального / максимального взвешенного края?

Question

Если у нас есть (произвольный) связный неориентированный граф G, ребра которого имеют различных весов,

1. содержит ли каждое MST из G минимальное взвешенное ребро?
2. существует ли MST G, который не содержит максимального взвешенного фронта?

Кроме того, я более благодарен, если кто-то может дать подсказку о ключевых вещах, которые следует иметь в виду при работе с такими вопросами MST.

Это проблема с домашним заданием. Спасибо.

Answer 1

есть ли MST G, который не содержит максимального взвешенного фронта?

Может быть, но не должно быть. Рассмотрим 4-вершинный граф следующим образом:

[A]--{2}--[B]
 |         |
 |         |
{1}       {3}
 |         |
 |         |
[C]-{50}--[D]

Минимальное остовное дерево состоит из набора ребер {CA, AB, BD}. Максимальный вес края равен 50, вдоль {CD}, но это не часть MST. Но если бы G уже была равна его собственному MST, то очевидно, что будет содержать свое собственное максимальное ребро.

содержит ли каждое MST из G минимальное взвешенное ребро?

Да. MST имеют свойство вырезать . A cut - это просто разбиение вершин графа на два непересекающихся множества. Для любого среза, который вы можете сделать, если вес ребра в этом срезе меньше, чем вес других ребер в срезе, то этот ребро принадлежит всем MST на графике. Поскольку вы гарантировали, что веса ребер различны, вы также гарантировали, что есть ребро, которое меньше всех остальных ребер.

Кроме того, я более благодарен, если кто-то может дать подсказку о ключевых вещах, которые следует иметь в виду при работе с такими вопросами MST.

Лучше всего рассуждать о вещах, использующих свойства MST в целом, и пытаться построить конкретные контрпримеры, которые, по вашему мнению, докажут ваш случай. Я привел пример каждой строки рассуждений выше. Из-за свойств обрезки и цикла вы всегда можете точно определить, какие ребра находятся в MST, поэтому вы можете систематически проверять каждое ребро, чтобы определить, находится ли оно в MST.

Answer 2

Содержит ли каждое MST из G минимальное взвешенное ребро?

Да. Предположим, что у нас есть MST, который не содержит минимальный край веса. Теперь включение этого ребра в MST приведет к cycle. Теперь в cycle всегда будет другое ребро, которое можно удалить, чтобы удалить цикл и при этом поддерживать график (MST) подключенным.

Есть ли MST группы G, которая не содержит максимального взвешенного ребра?

Зависит от графика. Если graph сам по себе является деревом, то нам нужно включить все его n-1 ребра в MST, поэтому нельзя исключить ребро максимального веса. Также, если край максимального веса равен cut-edge, так что его исключение никогда не приведет к соединению, тогда край максимального веса не может быть исключен. Но если край максимального веса является частью cycle, то его можно исключить из MST.

Answer 3

Я вижу, вы тоже учитесь на CSC263 через тест 2009? (То же самое здесь!)

Другой способ увидеть, что минимум всегда находится в MST, - просто взглянуть на это минимальное ребро (назовите его e):

          e 
v1 ---------------- v2

(Предположим, это связано с другими вершинами). Теперь, чтобы e НЕ быть включенным в окончательный MST означает, что в какой-то момент мы имеем, без потери общности, v1 в MST, но не v2. Однако единственный способ добавить v2 без добавления e состоит в том, чтобы сказать, что добавление v1 не добавит e в очередь (поскольку по определению e будет в верхней части очереди, поскольку оно имеет самый низкий приоритет), но это противоречит теореме построения MST.

По сути, невозможно, чтобы ребро с минимальным весом не попадало в очередь, а это значит, что оно было бы у любого построенного MST.

Answer 4

Для вашего первого вопроса ответ - нет, и алгоритм Крускала доказывает это. Он всегда будет выбирать минимальный край стоимости.

Для второго вопроса ответ - да, и найти примерный график просто:

1 - 2 (cost 10)
2 - 3 (cost 100)
3 - 1 (cost 1000)

Третье ребро никогда не будет выбрано, поскольку оно вводит цикл. В общем, если ребро с максимальной стоимостью создаст цикл, если его вставить в MST, он не будет вставлен.