Неотрицательная матрица весов

СВЯЗНОСТЬ

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

Теорема. Граф связен тогда и только тогда, когда его нельзя представить в виде объединения двух графов.

Пусть G(V,E) – связный граф, u и v – две его несмежные вершины. Две цепи < u, v > называются вершинно-непересекающимися, если у них нет общих вершин, отличных от u и v.

Теорема (Менгера). Пусть u и v – несмежные вершины в графе G. Наименьшее число вершин в множестве, разделяющем u и v равно наибольшему числу вершинно-непересекающихся простых < u,v >-цепей:

max|P(u,v) | = min|S(u,v)|

КРАТЧАЙШИЙ ПУТЬ МЕЖДУ ДВУМЯ ЗАДАННЫМИ ВЕРШИНАМИ s И t

Матрица весов

Пусть G= <X,Г> граф, дугам которого приписаны веса, задаваемые матрицей веса C = [c_ij] имеющий вид:

	x1	…	…	xn
x1	c11	…	…	c1n
…	…	…	…	…
…	…	…	…	…
xn	cn1	…	…	cnn

Неотрицательная матрица весов

Если матрица весов неотрицательна c_ij ≥ 0 , то кратчайший (s-t) -путь определятся наиболее эффективно алгоритмом Дейкстра.

Общие замечания.

1. При реализации алгоритма Дейкстра вершинам приписываются временные пометки.

2. Пометка вершины равна верхней границе длины пути от s к этой вершине.

3. Для алгоритма Дейкстра строится некоторая итерационной процедура.

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

6. Эта постоянная величина является точной длиной кратчайшего пути от s до рассматриваемой вершины.

Эта итерационная процедура является алгоритмом нахождения кратчайшего расстояния от s до рассматриваемой вершины. Среди таких алгоритмов рассмотрим алгоритм Дейкстра и алгоритм Беллмана.

Алгоритм Дейкстра (c_ij ≥ 0)

Этот алгоритм применяется, когда элементы матрицы весов неотрицательны.

Обозначим пометку вершины x_i через l(x_i).

Алгоритм состоит из трех блоков:

- присвоение начальных значений;

- обновления пометок;

- перевод пометок из временных в постоянные.

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

Шаг 1. Вершину, от которой ведем отсчет, обозначим через s.

Положить l(s) = 0 и считать эту величину постоянной, т.е. это - постоянная пометка.

Положить l(x_i) = ∞ для всех x_i ≠ s и считать эти пометки временными.

Положить p = s, где p – номер вершины, помеченной постоянной меткой.

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

Шаг 2. Для всех пометки, которых временные изменить пометки в соответствии со следующим выражением:

III. Перевод пометок из временных в постоянные.

Шаг 3. Среди всех вершин с временными пометками найти такую, для которой

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

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

Останов

Шаг 5 (ii)(Если требуется найти пути от s ко всем остальным вершинам). Если все вершины отмечены как постоянные, то эти пометки дают длину кратчайших путей.

Останов

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

Доказательство (набросок).

Допустим, что на некотором этапе постоянные пометки дают длины кратчайших путей. Пусть S₁ – множество вершин с этими пометками, а S₂ - множество вершин с временными пометками. В конце шага 2 каждой итерации временная пометка l(x_i) дает кратчайший путь от s к x_i, проходящей полностью по вершинам множества S₁.

Пример. Рассмотрим смешанный граф с 9 вершинами.

x₂ x₃

x₇

x₄

x₁

x₉ x₆

x₈ x₅

У этого графа неориентированное ребро рассматривается как пара противоположно ориентированных дуг равного веса. Задана матрица весов.

Матрица весов

	x1	x2	x3	x4	x5	x6	x7	x8	x9
x1
x2
x3
x4
x5
x6
x7
x8
x9

Найти все при помощи алгоритма Дейкстры кратчайшие пути от вершины x₁ ко всем остальным вершинам.

Постоянные пометки снабжать +, остальные пометки рассматриваются как временные.

Дата добавления: 2015-07-07