Существует ли минимальное связующее дерево, которое не содержит минуту взвешенный край / макс. взвешенный край?
Если у нас есть (произвольный) связанный неориентированный граф G, чьи края имеют отличные веса,
- каждый MST G содержит минимальный взвешенный край?
- существует ли MST G, который не содержит максимальный взвешенный край?
Кроме того, я более благодарен, если кто-то может дать подсказку ключевых вещей, нужно иметь в виду при контакте с такими вопросами о MST.
Это - проблема домашней работы.Спасибо.
4 ответа
существует ли MST группы G, которая не содержит максимально взвешенное ребро?
Может быть, но не обязательно. Рассмотрим четырехвершинный граф следующим образом:
[A]--{2}--[B]
| |
| |
{1} {3}
| |
| |
[C]-{50}--[D]
Минимальное остовное дерево состоит из множества ребер {CA, AB, BD}. Максимальный вес ребра составляет 50 вдоль {CD}, но он не является частью MST. Но если бы G уже был равен своему собственному MST, то, очевидно, он содержал бы свое собственное максимальное ребро.
каждый ли MST группы G содержит ребро с минимальным весом?
Да. MST имеют свойство сокращения . Разрез - это просто разбиение вершин графа на два непересекающихся множества. Для любого разреза, который вы можете сделать, если вес ребра в этом разрезе меньше, чем веса других ребер в разрезе, то это ребро принадлежит всем MST в графе. Поскольку вы гарантировали, что веса ребер различны, вы также гарантировали, что существует край, который меньше всех других ребер.
Кроме того, я буду более благодарен, если кто-то сможет намекнуть на ключевые моменты, которые следует иметь в виду, имея дело с такими вопросами MST.
Лучше всего рассуждать о вещах, используя свойства MST в целом, и пытаться построить конкретные контрпримеры, которые, по вашему мнению, докажут вашу правоту. Я привел пример каждой аргументации выше.Благодаря свойствам резки и цикла вы всегда можете точно определить, какие кромки находятся в MST, поэтому вы можете систематически тестировать каждую кромку, чтобы определить, находится ли она в MST.
На ваш первый вопрос ответ - нет, и алгоритм Крускала доказывает это. Он всегда выбирает ребро с минимальной стоимостью.
На второй вопрос ответ - да, и тривиально найти пример графа:
1 - 2 (cost 10)
2 - 3 (cost 100)
3 - 1 (cost 1000)
Третье ребро никогда не будет выбрано, так как оно вводит цикл. Таким образом, если ребро с максимальной стоимостью создаст цикл, если его вставить в MST, оно не будет вставлено.
Каждое ли MST группы G содержит ребро с минимальным весом?
Да. Предположим, у нас есть MST , который не содержит ребра минимального веса. Теперь включение этого ребра в MST приведет к циклу . Теперь в цикле всегда будет еще одно ребро, которое можно удалить, чтобы удалить цикл и по-прежнему поддерживать соединенным граф ( MST ).
Существует ли MST группы G, которая не содержит ребра с максимальным весом?
Зависит от графа. Если граф сам по себе является деревом, то нам нужно включить все его n-1 ребра в MST , поэтому ребро с максимальным весом не может быть исключено. Также, если край максимального веса является режущей кромкой , так что его исключение никогда не приведет к возможности соединения, тогда край максимального веса не может быть исключен. Но если край максимального веса является частью цикла , то его можно исключить из MST .
Я вижу, вы тоже изучаете CSC263 через тест 2009 года? (То же и здесь!)
Другой способ увидеть, что минимум всегда находится в MST, - это просто взглянуть на это минимальное ребро (назовите его e):
e v1 ------ ---------- v2
(Предположим, это связано с другими вершинами). Теперь, если e НЕ будет включен в окончательный MST, это означает, что в какой-то момент у нас есть, без ограничения общности, v1 в MST, но не v2. Однако единственный способ добавить v2 без добавления e - это сказать, что добавление v1 не добавило e в очередь (потому что по определению e будет наверху очереди, потому что у него самый низкий приоритет), но это противоречит теореме построения MST.
По сути, невозможно, чтобы ребро с минимальным весом не попало в очередь, а это означает, что оно будет иметь любой построенный MST.