Минимальный размерный график - отрицательный и положительный вес

Question

У меня возникли проблемы с пониманием того, будет ли MST деревом или нет.

Предположим, что при заданном графе G = (V, E) любое подмножество ребер T ⊆ E, которое связывает все вершины в V и имеет минимальный общий вес, должно быть деревом или может быть каким-то другим подграфом, когда - Некоторые ребра могут иметь отрицательные веса. - Все края имеют положительный вес.

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

Пожалуйста, помогите мне, если я прав или не прав.

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

Answer 1

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

EDIT Misunderstood Ваш вопрос немного:

Если у вас есть отрицательные веса: Это не может быть дерево

Все веса неотрицательны (> = 0): Существует минимальный порождающий дерево, но может быть и другое, что это не дерево и имеет ту же сумму весов.

Все веса положительные (> 0): Это дерево.

Answer 2

Некоторые факты, которые должны быть достаточно, чтобы ответить на ваш вопрос:

1. Если T является подмножество ребер, которое соединяет все вершины, то Т не является обязательно дерево.
2. Если T является подмножество ребер, которое соединяет все вершины, и T минимизирует сумму весов, то мы знаем:
   • T не обязательно являются уникальными.
   • T всегда содержит подмножество ребер, которые образуют дерево. («связность»)
   • Если все веса строго положительны, то T является деревом. («Минимальности»)
3. найти некоторые T с минимальной суммой весов так же просто, как найти в MST:
   • Найти некоторые MST (например, с помощью алгоритма Крускала или Прима).
   • Добавьте все края с отрицательным весом.

Тривиальный пример подмножества T, что сводит к минимуму вес для графа G = (V, E), где вес всех ребер равно -1, то Т Е.

Answer 3

Существует разница между минимальным остовным деревом/лесом (MST/F) и минимальным графом (MSG).

Минимальный охват граф (MSG): Соединяет все узлы во всех подключенных компонентах графа G, так что общие затраты минимальны.

Для неотрицательные расходы MSF соответствует MSG.

например. График G как треугольник с затратами 1 для каждого края. MSG соединит 3 вершины над 2 ребрами. И это тот же MSF, который вы получите путем вычисления G с Kruskal, Prim или Boruvka Algorithm.

Для отрицательные затраты MSF может быть неравным с соответствующим MSG, и, кроме того, MSG не всегда является MSF.

например. График G как треугольник с затратами -1 для каждого края. MSG будет использовать каждый край, потому что это уменьшит общие затраты. Поэтому вы получите цикл. И по определению дерево или лес не содержат циклов. С положительными затратами вы никогда не получите цикл в MSG, потому что добавление края, которое производит цикл, всегда будет увеличивать общие затраты MSG. Вычисление G с Kruskal, Prim или Boruvka вернет MSF.