Задачи о кратчайших путях

Докажите теорему 1: алгоритм Дейкстры находит SD от фиксированной вершины $(v)$ до любой вершины $i$ сети, если существует путь из $v$ в $i$.

С помощью алгоритма Дейкстры найдите древовидность кратчайших расстояний с корнем в вершине 1 ориентированной сети, показанной на рис. 5-8.

Fig. 5-8

С помощью алгоритма Дейкстры найдите древовидность кратчайших расстояний для сети, весовая матрица которой —

Докажите теорему 5.2: алгоритм Флойда—Уоршелла, использующий треугольную операцию, корректно решает задачу SD и SP.

Найдите матрицу SD и матрицу SP сети, весовая матрица $A$ которой —

Найдите матрицу SD и матрицу SP сети, весовая матрица которой —

В задаче 5.6 найдите SP из вершины 4 в вершину 2.

Постройте древовидность кратчайших расстояний с корнем в вершине 1 в сети из задачи 5.6, используя матрицу путей.

Пусть отрицательный элемент $(-1)$, встречающийся в четвёртом столбце весовой матрицы задачи 5.6, заменён меньшим отрицательным элементом $(-3)$. Найдите отрицательный цикл в изменённой сети.

В задаче 5.6 найдите матрицу расстояний и матрицу путей, которые дадут кратчайшее расстояние между каждой парой вершин с использованием путей, не использующих вершины 5, 6 и 7 в качестве промежуточных вершин. Используйте эти две матрицы, чтобы найти путь минимальной длины из вершины 7 в вершину 4, не использующий вершины 5 и 6 в качестве промежуточных вершин.

Докажите теорему 3: пусть $\left\{ 1,2,3, \ldots , n\right\}$ — множество вершин полного графа $G$ с неотрицательной весовой функцией $w$, удовлетворяющей неравенству треугольника $w(\left\{ i, j\right\} ) \leq w(\left\{ i, k\right\} )+w(\left\{ k, j\right\} )$ для любых трёх вершин $i, j$ и $k$. Если $W$ — множество из $m$ вершин сети $G$, существует дерево Штейнера для $W$ в сети, содержащее не более $(n-2)$ точек Штейнера.

Найдите дерево Штейнера для множества $W=\left\{ 1,2,3,4\right\}$ в сети, показанной на рис. 5-4.

Найдите точки Штейнера множества $\left\{ 1,3,5\right\}$ в сети из задачи 5.5.

Найдите медиану сети из задачи 5.5.

Найдите взвешенную медиану сети из задачи 5.5, если веса вершин равны $1, 0, 3, 3, 3$, 1 и 2 соответственно.

Найдите центр сети из задачи 5.5.

В сети минимальное значение эксцентриситета называется радиусом $\boldsymbol {r}(\boldsymbol {G})$, а максимальное значение — диаметром $\boldsymbol {d}(\boldsymbol {G})$. Покажите, что $r(G) \leq d(G) \leq 2 r(G)$.

Покажите, что если каждое ребро дерева имеет неотрицательный вес, мощность его центра (медианы) не превышает 2.

Перечислите дуги древовидности кратчайших расстояний с корнем в вершине 1 сети с $V=\left\{ 1,2,3,4,5,6\right\}$ и $E=\left\{ (1,2),(1,3),(1,4),(2,3),(2,5),(3,6),(4,5),(5,6)\right\}$ с весами $4,7,3,3,2,2,3$ и 2 соответственно.

Перечислите дуги древовидности кратчайших расстояний с корнем в вершине 1 сети с $V=\left\{ 1,2,3,4,5,6\right\}$ и $E=\left\{ (1,2),(1,5),(2,3),(2,4),(2,5),(3,4),(4,5),(4,6),(5,3)\right\}$ с весами $3,7,7,2,5,3,2,5$ и 1 соответственно.

Найдите матрицу SD $A_{5}$ и матрицу SP $P_{5}$ неориентированной сети с $V=\left\{ 1,2,3,4,5\right\}$ и $E= \left\{ \left\{ 1,2\right\} ,\left\{ 1,5\right\} ,\left\{ 2,3\right\} ,\left\{ 2,4\right\} ,\left\{ 3,4\right\} ,\left\{ 4,5\right\} \right\}$ с весами $1,4,5,1,2$ и 1 соответственно.

Найдите матрицу SD и матрицу SP сети со следующей весовой матрицей:

Найдите вес дерева Штейнера множества $\left\{ 1,2,3\right\}$ в сети, весовая матрица которой —