1.8. Определение экстремальных путей на графах.

Операции Шимбелла

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

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

(1)

2. Операция сложения двух величин а и b заменяется выбором из этих величин минимального (максимального) элемента, т.е.

, (2)

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

Метод Шимбелла.

С помощью операций Шимбелла длины кратчайших или максимальных путей между всеми вершинами определяются возведением в степень весовой матрицы Ω, содержащей веса рёбер. Например, элемент матрицы Ω² вычисляют следующим образом:

Аналогично находят элементы k–ой степени матрицы Ω.

Рис. 23

Пример. Составим для данного графа матрицу весов. Она определяет все маршруты, состоящие из одного ребра.

Найдём все кратчайшие пути из двух рёбер, для этого возведём эту матрицу в квадрат с учётом операций Шимбелла (min – кратчайшие пути).

Например,

Аналогично, длинами кратчайших путей из трёх рёбер будут элементы матрицы

и т.д. Например, длина кратчайшего пути из трёх рёбер из вершины D в вершину С равна 7. Это путь DBAC.

1.9. Порядковая функция орграфа без контуров.

Функция Гранди.

Рассмотрим орграф D = (V,X), не содержащий контуров, и определим множества V₀, V₁, , V_r:

(1)

           

где r – наименьшее число, такое, что

Множества V₀, V₁, , V_r называются уровнями орграфа D.

Функция O(v), определённая на множестве вершин V орграфа без контуров D = (V,X) и ставящая в соответствие каждой вершине номер уровня, которому она принадлежит, называется порядковой функцией орграфа D.

Пример 1. Разобьём орграф D, изображённый на рис. 24, на уровни и определим порядковую функцию O(v).

Решение. Согласно (1) имеем

Определив множества V₀, V₁, V₂, V₃, найдём значения порядковой функции O(v), (на рис. 24 они указаны при вершинах).

Рис. 24

Алгоритм нахождения уровней орграфа D = (V,X) без контуров

Шаг 1. Выпишем матрицу смежности A(D). Образуем под матрицей A(D) строку в i-ом месте которой укажем число единиц в i-ой строке матрицы A(D). Уровень V₀ образуют вершины, которым в строке соответствует число 0. Если V = =V₀, то задача решена и V₀ – единственный уровень графа D. В противном случае переходим к шагу 2.

Шаг 2. Образуем под строкой строку ставя под каждым нулём строки символ , а на любом другом i-ом месте – число единиц в i-ой строке матрицы A(D), не учитывая единицы в столбцах, находящихся над символами в строке . Уровень V₁ образуют вершины, которым в строке соответствует число 0. Полагаем j = 1.

Шаг 3. Пусть при некотором уже построены строки , , , по которым получены множества V₀, , V_j. Если строка состоит из нулей и символов , то задача решена и при r = j V₀, , V_r – уровни орграфа D. В противном случае переходим к шагу 4.

Шаг 4. Образуем под строкой строку , ставя под каждым нулём и символом строки символ , а на любом другом i-ом месте – число единиц в i-ой строке матрицы A(D), не учитывая единицы в столбцах, находящихся над символами в строке . Уровень V_j+1 образуют вершины, которым в строке соответствует число 0. Присваиваем j := j+1 и переходим к шагу 3.

Пример 2. Применив этот алгоритм, разобьём орграф D, описанный в примере 1 (см. рис. 24), на уровни.

Решение. Матрица смежности орграфа D, а также строки , , , , являющиеся результатом работы данного алгоритма, приведены в табл. 3. Из таблицы следует, что .

Таблица 3

	v1	v2	v3	v4	v5	v6
v1	0	0	0	0	0	1
v2	0	0	1	1	0	1
v3	1	0	0	1	1	0
v4	0	0	0	0	0	0
v5	0	0	0	0	0	1
v6	0	0	0	0	0	0
	1	3	3	0	1	0
	0	1	2		0
		1	0

Рассмотрим орграф D = (V,X). Функция g(v), ставящая в соответствие каждой вершине целое число , называется функцией Гранди для орграфа D, если в каждой вершине число g(v) является минимальным из всех целых неотрицательных чисел, не принадлежащих множеству , и g(v) = 0 при . .

Алгоритм определения функции Гранди для орграфов без контуров.

Разобьём множество вершин V орграфа D на уровни V₀, , V_r. По определению функции Гранди

(2)

Значения функции Гранди на каждом уровне V_i, где , однозначно находятся по её значениям на предыдущих уровнях V₀, , V_i-1 (поскольку а, следовательно, исходя из (2), её можно однозначно определить на всех последующих уровнях.

П ример 3. Найдём функцию Гранди для орграфа, описанного в примере 1. Разобьём множество вершин орграфа D на уровни: . С учётом (2) получаем g(v₄) = g(v₆) = 0, g(v₁) = g(v₅) = 1. Далее, для вершины имеем D(v₃) ={ v₁, v₄, v₅}, где g(v₄) = 0, g(v₁) = g(v₅) = 1, а, следовательно, g(v₃) = 2. Соответственно для вершины получаем D(v₂) ={ v₃, v₄, v₆}, где g(v₄) = g(v₆)= 0, g(v₃) = 2, а, следовательно, g(v₂) = 1. На рис. 25 приведено изображение орграфа D, около каждой вершины которого указано значение функции Гранди.

Рис. 25