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

Question

Создайте пример графика, где длина shortest path tree больше, чем минимальное остовное дерево.

В худшем случае, насколько длиннее может быть кратчайшее дерево путей, чем минимальное остовное дерево ?

Answer 1

Рассмотрим следующий график, где стоимость ребра записывается между скобками:

1 
| 
|(1) 
| 
2 
| \ 
| \ 
| \ 
| \ 
|(25) \ (10) 
|  \ 
3-------4  
    (20) 

Тогда кратчайший путь дерево с корнем в вершине 1 представляет собой:

1 
| 
|(1) 
| 
2 
| \ 
| \ 
| \ 
| \ 
|(25) \ (10) 
|  \ 
3  4  

в то время как минимальное покрывающее дерево от графика:

1 
| 
|(1) 
| 
2 
    \ 
    \ 
    \ 
    \ 
     \ (10) 
     \ 
3-------4  
    (20) 

Что касается вашего второго вопроса, я не мог придумать nswer.

Answer 2

Чтобы ответить на ваш второй вопрос: если граф имеет n вершин, длина дерева кратчайшего пути равна L, а длина минимального связующего дерева равна K, затем L < (n-1) K, но L может быть сколь угодно близко к (n-1) K. Чтобы понять, почему L < (n-1) K: каждый край в дереве кратчайшего пути меньше длины минимального связующего дерева. Из них (n-1), поэтому длина дерева кратчайшего пути меньше (n-1) K. Но разница может быть сколь угодно малой.

Рассмотрим график, где вершина 1 находится на расстоянии M, очень большое число, от вершины 2, ..., n. Расстояние любых двух вершин среди 2, ..., n - очень малое число e. Тогда длина дерева коротких путей, корневого в 1, равна (n-1) M, тогда как длина минимального связующего дерева равна (n-2) e + M. Отношение приблизительно (n-1), когда e равно очень маленький, а M очень большой.