Докажите, что подграф является минимальным остовным деревом - PullRequest
Новая
       34

Докажите, что подграф является минимальным остовным деревом

0 голосов
/ 31 октября 2018

Дано: 

G = (V,E)
T is an MST of G
G'=(V', E') ⊆ G
T' is an MST of G'

Докажите: 

(V',E∩T) is a subgraph of T'

Under what conditions is E∩T an MST of G'?

Вес ребер не обязательно должен быть четким.

Мой подход:

Применяя алгоритм Крускала к ребрам в E∩T, можно соединить ребра в порядке возрастания веса и одновременно гарантировать, что соединение не создаст цикл. Это даст MST, но можем ли мы показать, что этот MST является подграфом T'?

Имеет ли этот подход смысл? Поскольку я не использую тот факт, что T является MST G, у меня есть догадка, что я игнорирую что-то важное.

1 Ответ

0 голосов
/ 02 ноября 2018

Первое наблюдение: любой граф с числом узлов |V'| и количеством ребер, отличных от |V'|-1, не является деревом, поэтому одно из необходимых условий: |E∩T| = |V'|-1

Второе наблюдение: если T' равно MST G', то сумма его ребер минимальна среди всех возможных охватывающих деревьев G'. это означает, что если (V', E∩T) равно MST G', то сумма его ребер должна быть равна сумме ребер T'

Из наблюдений выше, необходимые и достаточные условия для того, чтобы (V', E∩T) был MST G':
1. |E∩T| = |V'|-1
2. sumofweigths((V', E∩T))=sumofweights(T')

Итак, в общем, вам нужно посчитать количество ребер в E∩T и сравнить с |V'|-1, а также вычислить сумму весов ребер в T' и сравнить с суммой весов ребер в E∩T

Однако у меня есть некоторые подозрения по поводу этой строки: (V',E∩T) is a subgraph of T'
Поскольку T' также имеет V' узлы, любой подграф T', кроме самого T', не будет деревом, и если это не дерево, он также не может быть MST. Вероятно, это (V',E∩T) is a subgraph of G' или (V',E∩T) is a subgraph of T, а не (V',E∩T) is a subgraph of T'?

...