Образуют ли кратчайшие пути от узла графа ко всем остальным дерево?

avatar
user16505641
8 августа 2021 в 21:45
48
1
0

Данный граф G с корневым узлом r образует ли кратчайшие пути от корня ко всем остальным вершинам дерево? Другими словами, если вы выберете кратчайший путь из r во все остальные вершины и объедините их, получится дерево?

Источник

Ответы (1)

avatar
templatetypedef
8 августа 2021 в 22:35
0

Да, почти.

Дерево кратчайших путей — это дерево с корнем в узле v, в котором прослеживаются кратчайшие пути от v до каждого другого узла.

Если вы выберете кратчайшие пути от узла v к другому узлу, это может не сформировать дерево, но это всегда будет DAG. Оно не всегда будет деревом, если существуют два или более разных кратчайших пути из v в некоторый узел u. Но в этом случае вы можете удалить некоторые ребра, чтобы преобразовать его в дерево.

user16505641
9 августа 2021 в 09:36
0

Подводя итог, если я найду кратчайший путь от корня к вершине u и кратчайший путь от корня к вершине v и объединим два пути, образующих дерево, это правильно?

templatetypedef
9 августа 2021 в 15:13
0

Не всегда. Если есть два разных кратчайших пути от r к u, и кратчайший путь от r к v проходит через u, вы можете получить DAG, не являющийся деревом. Но было бы легко преобразовать это в дерево.