Предложение для б): Ваш инстинкт говорит, что это неправильно, поэтому постарайтесь создать контрпример. Если вы найдете такой вариант, он будет урегулирован, в противном случае вы часто можете увидеть, почему утверждение истинно, проанализировав, почему ваша контрпример не удался. Я не говорю вам, правильный ли ваш ответ или ваш инстинкт.
Домашнее задание, конечно, должно быть давно, поэтому ответы:
Qa) Если G имеет цикл с уникальным самым тяжелым ребром e, то e не может быть частью любого MST.
True. Предположим, у вас есть связующее дерево 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) Алгоритм Прима работает с отрицательно взвешенными ребрами.
True. Одним из способов сделать это из правильности положительных весов является добавление постоянного веса 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''.
Общий вес T'' меньше, чем у T, поскольку T'' получается из T путем замены ребра на более легкий. T'' подключен (поскольку он был получен из T' путем удаления ребра цикла) и содержит V вершин и V - 1 ребер. Следовательно, это остовное дерево, и поэтому T не было минимальным.