Конкретный график и некоторые претензии на кратчайший путь?

Question

Я застрял в одном сложном вопросе, я читал на своих заметках.

неориентированный, взвешенный и связный граф G (без negative веса и все веса distinct) даются, мы знаем, в этом графике самый короткий путь между любой два Вершины находится на Minimum Spanning Tree (MST). (для любой пары вершин и для любого кратчайшего пути между ними она лежит на MST). Что из перечисленного является True?

1) График G - это дерево.

2) вес каждого {U, V} край, по меньшей мере, равна (то же самое), чтобы края в тяжелом кратчайшему пути от у к об.

3) кратчайший путь между любыми двумя вершиной у, v является уникальным.

4) предположим, что начало от вершины s, Prime (для расчета MST) и Дейкстрой (для вычисления кратчайшего пути), процесс и добавить вершины в свои деревья, с тем же порядком. (два алгоритма работают с одним и тем же порядком в обрабатывающем и добавляющем узле)

Как проверить эти параметры? Это сложный вопрос.

Answer 1

1. No. Например: V = {1, 2, 3}, E = {(1, 2, 1), (2, 3, 2), (1, 3, 4)} (каждое ребро кодируется как кортеж (одна вершина, другая вершина, вес)). Это не дерево, но самый короткий путь находится на минимальном остовном дереве.

2. Да. Если вес этого ребра меньше, чем вес самого тяжелого края, который находится в кратчайшем пути, этот край короче кратчайшего пути (потому что нет ребер с отрицательным весом). Таким образом, кратчайший путь не является самым коротким. Это противоречие.

3. No *. Предположим, что у нас есть граф с двумя вершинами {1, 2} и один край между ними с нулевым весом. Есть бесконечно много кратчайшего пути между первой и второй вершины ([1, 2], [1, 2, 1, 2], ...)

   * Тем не менее, есть уникальный простой кратчайший путь между любыми двумя вершинами, потому что есть только один простой путь между любыми двумя вершинами в дереве , любой путь, который не полностью лежит в минимальном остовном дереве, длиннее из-за оператора задачи и существует только одно минимальное связующее дерево в графе с разным весом ребер.

4. Нет. Рассмотрим это дерево: V = {1, 2, 3, 4}, E = {(1, 2, 3), (2, 3, 2), (1, 4, 4)}. Предположим, что начальная вершина равна 1. Алгоритм Прима будет принимать первую вершину, чем вторую, а третью - только после этого четвертую. Но алгоритм Дейкстры займет четвертую вершину перед третьей. Это происходит потому, что третья вершина расположена ближе к дереву после обработки первых двух вершин, но общее расстояние до него от стартового узла больше.

Answer 2

Я не хочу, чтобы дать полный ответ, но вот как подойти к нему:

1. Вы можете добавить край [ы] к дереву таким образом, что это не дерево больше, и до сих пор Дерево содержит все кратчайшие пути?

2. Что произойдет, если есть край, который короче самого тяжелого края?

3. это запутанно, потому что проблема говорит, что «кратчайший путь между любыми двумя вершинами находится на MST», но не учитывает тот факт, что могут быть несколько кратчайших путей. Поэтому вы можете предположить, что «по крайней мере один короткий путь лежит на дереве». В этом случае просто соедините две вершины с ребром, вес которого равен стоимости через MST, и вы получите ответ.

4. Опять же, вы должны начать с того, что произойдет, если вершины не добавляются в том же порядке