2020-04-07
190
Пример 1. Пусть задан граф G, показанный на рис. 15.23. Подсчитать количество маршрутов длиной 3 в данном графе.
Решение: Запишем матрицу смежности графа G:
.
Как уже было показано ранее, чтобы найти число маршрутов длиной 2, в заданном графе необходимо возвести его матрицу смежности в квадрат. Алгебраическое произведение матриц определяется по формуле
r 2 ij = 
aik bki,
где r 2 ij ─ элемент матрицы R2.
Вычислив, таким образом, значения всех элементов, мы придем в итоге к следующей матрице:
.
Для того, чтобы определить количество маршрутов длиной 3 в исходном графе, необходимо полученную на первом шаге матрицу R2 умножить на R. Например,
r 31,2 = r 1,1 r 21,2 + r 1,2 r 22,2 + r 1,3 r 23,2 + r 1,4 r 24,2 = 0*0 + 1*2 + 2*3 + 0*0 = 4.
Используя вышеуказанную формулу умножения матриц, получим:
.
Из полученной матрицы R3 следует, что в исходном графе между вершинами, например, x 1 и x 2, существует 4 маршрута длиной 3: S1 = (x 1, x 2)(x 2, x 1)(x 1, x 2); S2 = (x 1, x 2)(x 2, x 4)(x 4, x 2); S3 = (x 1, x 3)(x 3, x 1)(x 1, x 2); S4 = (x 1, x 3)(x 3, x 4)(x 4, x 2).
Пример 2. Для графа, изображенного на рис. 15.29, привести примеры маршрута, цепи, цикла, простой цепи и простого цикла.
|
|
|
Рис. 15.29. Пример графа G
Ответ: Маршрутом в графе является любая конечная последовательность ребер, причем маршрут может проходить через одну и ту же вершину или ребро любое число раз. Тогда в качестве маршрута можно принять такую конечную последовательность: S = (x 1, x 2), (x 2, x 6), (x 6 ─ x 2), (x 2 ─ x 7), (x 7 ─ x 6), (x 6 ─ x 2). Цепью называют маршрут, не имеющий повторяющихся ребер. Таким образом, последовательность S = (x 1, x 2), (x 2, x 4), (x 4, x 6), (x 6, x 2), (x 2, x 7) можно считать цепью. Цикл представляет собой замкнутую цепь, т. е. цепь, у которой первая и последняя вершины совпадают. Тогда последовательность C = (x 1, x 5), (x 5, x 3), (x 3, x 1), (x 1, x 8), (x 8, x 5), (x 5, x 1) является циклом. При это, как мы видим, цепь и цикл могут проходить несколько раз через одну и ту же вершину. Простая цепь (цикл) не может включать в себя ни повторяющихся ребер, ни вершин. Примером простой цепи может служить последовательность S = (x 1, x 2), (x 2, x 4), (x 4, x 6), (x 6, x 8), (x 8, x 3); а простой цикл C = (x 1, x 5), (x 5, x 3), (x 3, x 1).
Пример 3. Для графа, заданного на рис. 15.30 привести пример разреза, правильного разреза.
Ответ: Правильными разрезами будут: U1 = {(x 3, x 6), (x 4, x 6), (x 4, x 7); U2 = {(x 4, x 10), (x 5, x 10)}; U3 = {(x 5, x 12)}; U4 = {(x 5, x 15)}. А разрез U определяется как их объединение: U = U1 È U2 È U3 È U4.
Рис. 15.30. Пример графа G
