Задачи на взвешенном графике, ИСТИНА/ЛОЖЬ + объяснение

Предложение для б): Ваш инстинкт подсказывает, что это неправильно, поэтому попытайтесь привести контрпример. Если вы его найдете, значит, оно решено, в противном случае вы часто можете понять, почему утверждение верно, проанализировав, почему ваше построение контрпримера потерпело неудачу. Однако я не говорю вам, верен ли ваш ответ или ваш инстинкт.

Домашнее задание, безусловно, нужно было сделать уже давно, поэтому ответы:

Qa) Если в G есть цикл с единственным самым тяжелым ребром e, то e не может быть частью ни одного MST.

Истинный. Предположим, у вас есть связующее дерево T, содержащее ребро e. Если удалить из дерева ребро e, получится граф с двумя непустыми компонентами связности C1 и C2. По крайней мере одно из других ребер в цикле должно соединять C1 и C2 (иначе это не был бы цикл). Пусть g будет таким ребром. Дерево T', полученное из T удалением e и добавлением g, является остовным деревом с меньшим весом, чем T. Следовательно, T не был MST.

Qb) Дерево кратчайших путей, вычисленное алгоритмом Дейкстры, обязательно является MST.

Мой ответ верен, но мой инстинкт подсказывает мне, что что-то не так.

Инстинкт был прав, это ложь. Рассмотреть возможность

    6
  A---B
3 |   | 1
  C---D
    3

где дерево кратчайших путей вычисляется из вершины A. Дерево кратчайших путей это

    6
  A---B
3 |
  C---D
    3

с общим весом 12, но уникальный MST

  A   B
3 |   | 1
  C---D
    3

с весом 7.

Qc) Алгоритм Прима работает с ребрами с отрицательным весом.

Истинный. Один из способов вывести это из правильности положительных весов — добавить постоянный вес W ко всем ребрам, чтобы все веса рёбер были положительными (например, W = 1 + max { |weight(e)| : e ∈ E }).

Поскольку дерево с V вершинами всегда имеет V - 1 ребер, общие веса любого остовного дерева различаются на (V - 1)*W между модифицированными и немодифицированными весами, поэтому дерево является MST для модифицированных весов тогда и только тогда, когда оно равно единице для немодифицированных весов ребер. .

Порядок ребер по весу не меняется при добавлении константы ко всем весам, поэтому алгоритм Прима строит то же остовное дерево для измененных весов ребер, что и для немодифицированных весов, в той же последовательности.

По корректности для положительных весов дерево, построенное по алгоритму Прима с модифицированными весами, является MST для модифицированных весов.

Qd) Если в G есть цикл с единственным самым легким ребром e, то e должно быть частью каждого MST.

ЛОЖЬ. Рассмотреть возможность

     1   1
   A---B---C
   |  / \  |
 1 | /4 5\ | 1
   |/  6  \|
   D-------E

Цикл BDE имеет единственное самое легкое ребро BD веса 4, но MST не содержит ни одного из ребер этого цикла.

Однако если в графе G есть уникальное самое легкое ребро e , оно должно быть частью каждого MST. Это двойственно а): рассмотрим остовное дерево T из G, которое не содержит e. Добавляя e к T, мы получаем граф T', который должен иметь цикл (поскольку T был остовным деревом, а e не входит в T). Любой цикл в T' должен содержать e, иначе это будет цикл в T. Итак, выберите любой цикл C в T' (есть ровно один, но это не важно) и удалите любое ребро, кроме e, из C. Пусть полученный граф будет T''.