Поддерево кратчайшего пути Дерево также является кратчайшим деревом?

У меня есть неориентированный взвешенный граф G=(V,E), где V представляют узлы, а E представляют ребра. С помощью алгоритма Дейкстры я получил дерево кратчайших путей Ts=(s,V) с корнем в исходном узле s и охватывающее все узлы V в графе G. Затем я выбрал поддерево Tm=(s,K), (где K является подмножеством V) дерева кратчайших путей Ts=(s, V), которые соединяют s только с K узлами среди всех V узлов, т. е. поддерево Tm является подмножеством дерева кратчайших путей Ts.

Мой вопрос заключается в том, как теперь я могу доказать с помощью аргументов или леммы/теоремы, что это поддерево Tm дерева кратчайших путей Ts также является кратчайшим деревом? Заранее спасибо.


algorithm tree undirected-graph dijkstra
person Ali    schedule 28.12.2016    source источник
comment
Каково именно ваше определение многоадресного дерева и какова его конструкция? Сказать, что новое результирующее дерево недостаточно, чтобы понять, что вы делаете.   -  person Paul Hankin    schedule 28.12.2016

Ответы (2)


arrow_upward
0
arrow_downward

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

Затем, если вы выберете какое-то поддерево исходного SPT, вам придется сохранить свойства дерева, тогда у нас есть несколько случаев:

  • Тривиальное дерево: всего один узел, без ребер

    no problems in here, it's a SPT (empty)

  • Нетривиальное дерево: два или более узлов, очевидно, с ребрами.

    this is kind of tricky. 

if you suppose that this sub-tree is rooted on source, then its easy
to see that the sub-tree will be a set of shortest paths between
the source and the other nodes, making it be a SPT ROOTED ON SOURCE.

otherwise, it wont be a SPT, cause if its rooted on some other node
(instead of source), the path from the root to other node (different
from source) may not be minimum.

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

person Daniel    schedule 28.12.2016

arrow_upward
0
arrow_downward

Поскольку вопрос недостаточно ясен, я предполагаю, что ваш вопрос следующий:

Если Ts=(s,V) — дерево кратчайших путей (с корнем в s) графа G = (V,E,W), то докажите, что Ts = (s, K), поддерево Ts, индуцированное K ( \subset V) — это дерево кратчайших путей (с корнем в s) подграфа G' = (K,E',W) графа G, индуцированное K.

Доказать можно от противного.

Доказательство (неформальное). Пусть u \in K — вершина. Поскольку u также принадлежит V, путь p = s -> u, заданный Ts, является кратчайшим. Предположим, что T's не является деревом кратчайших путей G'. Тогда путь p = s -> u, заданный T's, не является кратчайшим в G'. Это означает, что существует другая вершина v (\in K), такая, что p не содержит v и v создает ярлык типа s -> v -> u.

Поскольку путь p = s -> u, заданный Ts, является кратчайшим в G, p должен содержать v где-то между s и u, что приводит к противоречию.

person naheed    schedule 17.06.2018