Отрицательные границы веса

Question

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

Мой ответ: поскольку ребра соединяют все вершины, это должно быть дерево. На графике вы можете удалить один из ребер и все еще подключить все вершины. Кроме того, отрицательные ребра могут быть разрешены на графике (например, алгоритмы Prim и Kruskal).

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

Answer 1

Во-первых, дерево - это тип графика. Итак, «На графике вы можете удалить один из ребер и все еще подключить все вершины», это неверно. Дерево - это график без циклов, т. Е. Только один путь между любыми двумя узлами.

Отрицательные веса вообще могут существовать либо в дереве, либо в графе.

Способ решения этой проблемы заключается в том, чтобы показать, что если у вас есть граф, который соединяет все компоненты, но не является деревом, то он также не имеет минимального веса (т. Е. Есть другой график, который делает то же самое вещь с меньшим общим весом.) Этот вывод справедлив только в том случае, если граф содержит только положительные ребра, поэтому вы также должны предоставить контрпример - график, который НЕ является деревом, которое имеет минимальный вес и которое полностью подключено.

Answer 2

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

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