Примеры решения задач
Пример 1. Пусть задан граф G, показанный на рис. 15.23. Подсчитать количество маршрутов длиной 3 в данном графе.
Решение: Запишем матрицу смежности графа G:
.
Как уже было показано ранее, чтобы найти число маршрутов длиной 2, в заданном графе необходимо возвести его матрицу смежности в квадрат. Алгебраическое произведение матриц определяется по формуле
r2ij
=
aik
bki,
где r2ij ─ элемент матрицы R2.
Вычислив, таким образом, значения всех элементов, мы придем в итоге к следующей матрице:
.
Для того, чтобы определить количество маршрутов длиной 3 в исходном графе, необходимо полученную на первом шаге матрицу R2 умножить на R. Например,
r31,2 = r1,1r21,2 + r1,2r22,2 + r1,3r23,2 + r1,4r24,2 = 0*0 + 1*2 + 2*3 + 0*0 = 4.
Используя вышеуказанную формулу умножения матриц, получим:
.
Из полученной матрицы R3 следует, что в исходном графе между вершинами, например, x1 и x2, существует 4 маршрута длиной 3: S1 = (x1, x2)(x2, x1)(x1, x2); S2 = (x1, x2)(x2, x4)(x4, x2); S3 = (x1, x3)(x3, x1)(x1, x2); S4 = (x1, x3)(x3, x4)(x4, x2).
Пример 2. Для графа, изображенного на рис. 15.29, привести примеры маршрута, цепи, цикла, простой цепи и простого цикла.
Рис. 15.29. Пример графа G
Ответ: Маршрутом в графе является любая конечная последовательность ребер, причем маршрут может проходить через одну и ту же вершину или ребро любое число раз. Тогда в качестве маршрута можно принять такую конечную последовательность: S = (x1, x2), (x2, x6), (x6 ─ x2), (x2 ─ x7), (x7 ─ x6), (x6 ─ x2). Цепью называют маршрут, не имеющий повторяющихся ребер. Таким образом, последовательность S = (x1, x2), (x2, x4), (x4, x6), (x6, x2), (x2, x7) можно считать цепью. Цикл представляет собой замкнутую цепь, т. е. цепь, у которой первая и последняя вершины совпадают. Тогда последовательность C = (x1, x5), (x5, x3), (x3, x1), (x1, x8), (x8, x5), (x5, x1) является циклом. При это, как мы видим, цепь и цикл могут проходить несколько раз через одну и ту же вершину. Простая цепь (цикл) не может включать в себя ни повторяющихся ребер, ни вершин. Примером простой цепи может служить последовательность S = (x1, x2), (x2, x4), (x4, x6), (x6, x8), (x8, x3); а простой цикл C = (x1, x5), (x5, x3), (x3, x1).
Пример 3. Для графа, заданного на рис. 15.30 привести пример разреза, правильного разреза.
Ответ: Правильными разрезами будут: U1 = {(x3, x6), (x4, x6), (x4, x7); U2 = {(x4, x10), (x5, x10)}; U3 = {(x5, x12)}; U4 = {(x5, x15)}. А разрез U определяется как их объединение: U = U1 U2 U3 U4.
Рис. 15.30. Пример графа G
Вопросы для самоконтроля
1. Что из себя представляет маршрут в графе?
2. Как определяется длина маршрута?
3. Что такое маршрут в графе. Как определяется длина маршрута?
4. Дайте определение цепи, цикла, простого цикла и простой цепи в графе.
5. Какой граф называется связным?
6. Что такое компонента связности?
7. Что такое блок графа?
8. Дайте определение разреза, правильного разреза графа. Приведите примеры.
9. Дайте определение вершинной связности. Приведите примеры.
10. Дайте определение реберной связности. Приведите примеры.