Учитывая граф G, работает ли принцип «разделяй и властвуй» для поиска минимальных остовных деревьев? - PullRequest
Новая
       33

Учитывая граф G, работает ли принцип «разделяй и властвуй» для поиска минимальных остовных деревьев?

0 голосов
/ 02 апреля 2012

Если дан связный граф G, разбейте его на Ga и Gb.Если вы найдете минимальное остовное дерево для Ga и Gb (называемое Xa и Xb соответственно), образует ли связующее Xa с Xb минимальное взвешенное ребро еще остовное дерево?Является ли это связующее дерево минимальным остовным деревом?

Это моя логика до сих пор.Я полагаю, что соединение Xa с Xb сформирует по крайней мере связующее дерево почти по определению.(Если есть контрпример, хотя это было бы полезно) Однако, я не думаю, что это всегда будет формировать минимальное остовное дерево, потому что в зависимости от структуры графа вы можете удалить ребро из Xa или Xb,затем добавьте ребро, соединяющее их, и у вас останется дерево.Это может иметь место в ситуации, когда несколько ребер одного веса соединяют Xa и Xb в разных вершинах.

Правильна ли моя логика до сих пор?

Ответы [ 2 ]

1 голос
/ 02 апреля 2012

Это правильно, что вы не всегда получаете минимальное связующее дерево, просто соединяя Xa и Xb.Но не обязательно, чтобы ребра, соединяющие Xa и Xb, имели одинаковый вес.См. Следующий пример:

Предположим, у вас есть следующий график G: 

A-B-C-D 
| | | | 
E-F-G-H

Край (B, C) имеет стоимость 1 и (F, G) имеет стоимость 2, все остальные ребрастоимость 10.

Затем вы делите его на Ga и Gb: 

A-B   C-D 
| |   | | 
E-F   G-H

Минимальные остовные деревья Xa и Xb: 

A-B   C-D 
|       | 
E-F   G-H

Если вы теперь соедините ихс минимально возможным краем вы получаете остовное дерево со стоимостью 61: 

A-B-C-D 
|     | 
E-F G-H

Но это не минимальное остовное дерево.Минимальное связующее дерево (с затратами 53) будет 

A-B-C-D 
|       
E-F-G-H
0 голосов
/ 02 апреля 2012

Не совсем. Вы должны принять решение и перепроверить контрпример. Например, предположим, что для графа G минимальное остовное дерево - X.

  • Если вы разделите график так, что вы прорежете X только один раз, тогда минимальное взвешенное ребро обязательно будет удаленным ребром, и, таким образом, вы не сможете построить контрпример.
  • Однако, если ваш раздел разрезает дерево в двух местах, у вас есть контрпример. Вы утверждаете, что вам нужно будет добавить только одно ребро, но по построению вы обрезаете оптимальное дерево в двух местах, и, таким образом, вам нужно добавить два ребра, чтобы восстановить оптимальное дерево (и у вас также был посторонний край в одном из ваших перегородки). (См. Ответ Штекла для наглядного примера.)

Ваше первое утверждение («Я полагаю, что соединение Xa с Xb сформировало бы, по крайней мере, связующее дерево почти по определению»), верно; Вы можете доказать это, используя некоторые факты о деревьях: полносвязный граф с N узлами и N-1 ребрами - это дерево, а дерево - полносвязный граф с N узлами и N-1 ребрами (циклы не могут образовываться). Или вы можете использовать эквивалентное условие от http://en.wikipedia.org/wiki/Tree_(graph_theory)#Definitions

...