§ 2.10.2. Кратчайший (s t)-путь. Случай неотрицательной матрицы весов

Наиболее эффективный алгоритм решения задачи о кратчайшем (s t)-пути дал Дейкстра. Этот метод основан на приписывании вершинам временных пометок, причём пометка вершины даёт верхнюю границу длины пути от s-ой к данной вершине. Эти пометки постепенно уменьшаются с помощью некоторой итерационной процедуры, и на каждом шаге итерации точно одна из временных пометок становится постоянной. Этот факт указывает на то, что пометка уже не является верхней границей, а даёт точную длину кратчайшего пути от s-ой к рассматриваемой вершине.

Алгоритм Дейкстры (c_ij>=0)

Пусть l(x_i) – пометка вершины x_i

Присвоение начальных значений

Шаг 1. Положить l(s)=0 и считать эту пометку постоянной. Положить l(x_i)= для любого x_i  0 и считать эти пометки временными. Положить p=s.

Обновление пометок

Шаг 2. Для всех x_iГ(p), пометки которых временные, изменить пометки в соответствии с правилом:

l(x_i)=min[l(x_i), l(p)+с(p,x_i)] (1)

Превращение пометок в постоянные

Шаг 3. Среди всех вершин с временными пометками найти такую, для которой l(x_i^*)=min[l(x_i)]

Шаг 4. Считать пометку вершины x_i^* постоянной и положить p = x_i^* .

Шаг 5. а – если надо найти (s t)-путь

Если p = t, то l(p) является длиной кратчайшего пути. Останов.

Если p  t, то перейти к шагу 2.

b – если надо найти пути от s ко всем остальным вершинам

Если все вершины отмечены как постоянные, то эти пометки дают длины кратчайших путей. Останов.

Если некоторые пометки являются временными, перейти к шагу 2.

§ 2.10.4. Наиболее надёжный путь

В задаче о кратчайшем пути в качестве длины пути бралась сумма весов дуг, образующих этот путь.

Рассмотрим случай, когда вес дуги представляет её надёжность. В случае физических систем надёжность дуги – это вероятность того, что она находится в работоспособном состоянии. Надёжность (s t)-пути, составленного из дуг, взятых из множества Р, можно записать формулой:

(Р) =  _ij, (2)

для всех (x_i x_j)P

Здесь _ij - надёжность дуги (x_i x_j).

Задачу о нахождении наиболее надёжного пути можно свести к задаче о кратчайшем (s t)-пути, взяв логарифм произведения (2)

§ 2.11. Деревья

§ 2.11.1. Типы деревьев

Опр.6. Неориентированное дерево – это:

1. связанный (n,m)-граф, причём m=n-1;

2. связанный граф, не имеющий циклов;

3. граф, в котором каждая пара вершин соединена одной и только одной простой цепью

Все эти определения равнозначны. Убедимся в этом.

Любая иерархическая структура представляется неориентированным деревом.

Опр.7 Пусть G=(V,E) – неориентированный граф с n вершинами. Остовным деревом (или остовом) графа G называется всякий остовной подграф графа G, являющийся деревом.

Пример 9.

Исходный граф G Остов графа G. Другой остов графа G

Остов графа G можно рассматривать как минимальный связный остовной подграф графа G, где минимальность понимается так, что никакое собственное подмножество рёбер этого остова не образует связный остовной подграф графа G.

Опр.8 Ориентированное дерево (древовидность) представляет собой ориентированный граф без циклов, в котором полустепень захода каждой вершины, за исключением одной, называемой корнем, равна 1, а полустепень захода корневой вершины равна 0.

Пример 10.

Ориентированное дерево с вершиной в х₁

Как видно из определения, ориентированное дерево с n вершинами имеет n-1 дуг и связано.

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

Н е всякий ориентированный граф содержит остовное ориентированное дерево. Это подтверждает следующий пример.

Пример.

В этом примере орграф содержит две вершины, имеющие полустепень захода, равную 0. Для данного графа невозможно построить остовное ордерево.

Неориентированное дерево можно преобразовать в ориентированное: надо взять его произвольную вершину в качестве корня и рёбрам приписать такую ориентацию, чтобы каждая вершина соединялась с корнем только одной простой цепью.

Возможно обратное преобразование. Если T=(X,B) – ориентированное дерево, тоT=(X,B) – неориентированное дерево. B здесь – множество дуг дерева Т без учёта их ориентации.