Дискретная математика:
логика, группы, графы, фракталы

Акимов О.Е.

3.2. Морфология графа

Пути и контуры в графе

Сама матрица смежности A(Г₀) дает число путей, длина которых равна единице. Квадрат матрицы смежности A²(Г₀) дает число путей, длина которых равна двум дугам. Куб матрицы A³(Г₀) дает число путей в три дуги и т.д. В частности, на пересечении 2-го столбца и 3-ей строки матрицы A³(Г₀) стоит 3. Это означает, что из вершины 3 в вершину 2 имеется три пути, а из вершины 2 в вершину 3 существует уже четыре пути в три дуги:

A²(Г₀) = ,     A³(Г₀) = ,

A⁴(Г₀) = ,   A⁵(Г₀) = .

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

A(Г₀) = ,     A'(Г₀) = .

Матрица A'(Г₀) нужна для получения соответствующей степени матрицы A(Г₀). Так,

A(Г₀) · A'(Г₀) = A²(Г₀),      A²(Г₀) · A'(Г₀) = A³(Г₀), ...

В чем преимущество означенной матрицы перед матрицей смежности? Означенная матрица Aⁿ помимо числа путей указывает еще и вершины, через которые эти пути пролегают. На диагонали матрицы Aⁿ будут указаны всевозможные контуры, длина которых равна 1, 2, 3 и т.д. дугам. Неповторяющиеся вершины для отдельных путей укажут на элементарные пути. Так как в нашем графе Г₀ (рис. 3.14) имеется шесть вершин, то элементарных путей, длина которых равнялась бы шести дугам, вообще быть не может. Отсюда максимальная степень означенной матрицы для определения всех гамильтоновых путей должна быть равна пяти. В нашем графе Г₀, как на то указывает матрица A⁵(Г₀), только три гамильтоновых пути: {3, 2, 6, 4, 5, 1};  {4, 5, 1, 6, 2, 3} и {2, 3, 5, 1, 6, 4}. На диагонали матрицы A⁶(Г₀) стоит один и тот же гамильтонов контур {1, 3, 2, 6, 4, 5, 1}, который всякий раз начинается с новой вершины.

A²(Г₀) = A(Г₀) · A'(Г₀) = ,

A³(Г₀) = A²(Г₀) · A'(Г₀) = .

При получении следующих степеней означенных матриц оставим только гамильтоновы пути и контуры:

A⁴(Г₀) = ,

A⁵(Г₀) = ,

A⁶(Г₀) = .