Задания для самостоятельной работы

1. Приведите примеры задания графа различными способами: аналитическим, графическим, матричным.

2. Задайте графическим и матричным способами ориентированный, неориентированный и смешанный граф.

3. Задайте произвольный граф G = (X, U), |X| = 9, |U| = 24 и запишите для него матрицу смежности и инцидентности, а также его списковое представление.

4. Приведите словесный описания и составьте структурную схему алгоритма перехода от матрицы инцидентности к матрице смежности и наоборот.

5. Определите количество ре бер в полном графе K₁₅ без петель.

6. Постройте Платоновы графы.

7. Задайте Платоновы графы на основе матриц смежности и инцидентности.

8. Задан произвольный граф G = (X, U), где ½X½=6; ½U½=10. Постройте двойственный ему граф G_S.

9. Приведите пример мультиграфа и определите его мультичисло.

10. Приведите примеры нечетких неориентированных графов первого и второго рода.

 

Понятие графа опирается на понятие множества. Графом можно назвать объект, состоящий из двух множеств: точек и линий, которые находятся между собой в некотором отношении. Множество точек графа обозначается X = { x ₁, x ₂, …, x _n } и называется множеством вершин. Множество линий, соединяющих любые пары вершин (x_i, x_j) Î X, называется множеством ребер или дуг и обозначается U = { u ₁, u ₂, …, u _m }.

Маршруты, цепи, циклы

Маршрутом в графе G = (X, U) называется некоторая конечная последовательность ребер вида S = (x ₀, x ₁), (x ₁, x ₂), …, (x_{l -1}, x_l), где x ₀, x_l ─ ─соответственно его начальная и конечная вершины. Очевидно, что в конечном графе G можно выделить только конечное число маршрутов. Число ребер в маршруте S называется его длиной. Существует простой способ определения маршрутов длиной q по матрице R графа G путем возведения ее в q -ю степень.

Например, пусть задана матрица R графа G (рис. 15.23):

	1	2	3	4
1	0	1	1	0	.
R = 2	1	0	0	1
3	1	0	0	1
4	0	1	1	0

 

Рис. 15.23. Пример графа G

Возведем ее в квадрат по правилу:

                         r ² _i,j = r_1,i * r_{j ,1} + r _{2, i} * r_{j ,2} +... + r_{n , i} * r_{j , n}.                        (1.4)

Тогда для рассматриваемого в данном примере графа, к примеру, элемент r ²₁₁ матрицы R² будет иметь следующее значение:

r ² _{1, 1} = a ₁₁ b ₁₁ + a ₁₂ b ₂₁ + a ₁₃ b ₃₁ + a ₁₄ b ₄₁ = 0 + 1*1 + 1*1 + 0 = 2.

А, например, r ²_3,3 = r _1,3 r _3,1 + r _2,3 r _3,2 + r _3,3 r _3,3 + r _4,3 r _3,4 = 1*1 + 0*0 + 0*0 + 1*1 = 2.

	1	2	3	4
1	2	0	0	2	.
R2 = 2	0	2	2	0
3	0	2	2	0
4	2	0	0	2

Каждый r_{i , j} элемент R² равен числу маршрутов длиной 2, ведущих из вершины x_i в x_j. Например, r _3,2 = 2 означает, что в графе два маршрута ведущих из x ₃ в x ₂ длиной 2: S₁ = (x ₃, x ₁), (x ₁, x ₂); S₂ = (x ₃, x ₄), (x ₄, x ₂).

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

Маршрут, в котором нет повторяющихся ребер, называется цепью. Замкнутая цепь, в которой x ₀ = x_l, называется циклом. Соответственно цепи и циклы называются простыми, если они не содержат повторяющихся вершин, кроме, разумеется, первой и последней в случае цикла. В графе G (см. рис. 15.14, a):

S₁ = (x ₁, x ₂), (x ₂, x ₃), (x ₃, x ₆), (x ₆, x ₂), (x ₂, x ₄) ─ маршрут,

S₂ = (x ₁, x ₂), (x ₂, x ₃), (x ₃, x ₆), (x ₆, x ₂) ─ цепь,

S₃ = (x ₆, x ₂), (x ₂, x ₄), (x ₄, x ₁), (x ₁, x ₂), (x ₂, x ₃), (x ₃, x ₆) ─ цикл,

S₄ = (x ₁, x ₂), (x ₂, x ₃), (x ₃, x ₇), (x ₇, x ₆) ─ простая цепь,

S₅ = (x ₁, x ₂), (x ₂, x ₃), (x ₃, x ₇), (x ₇, x ₆), (x ₆, x ₅), (x ₅, x ₄), (x ₄, x ₁) ─ простой цикл.

Цикл длиной 3 называется треугольником.

Связный регулярный граф степени 2 называется циклическим графом или циклом. Циклический граф с n вершинами обозначается C_n (рис. 15.24, а).

                           

а                                                   б

Рис. 15.24 Циклический граф (а), граф-колесо (б)

Соединение графов К₁ и С_n-1 (n ³ 3) называется колесом с n вершинами и обозначается W_n. На рис. 15.24, б показано колесо W₆.

Две произвольные вершины x_i, x_j Î X графа называются связными, если существует маршрут S, в котором концевыми будут вершины x_i, x_j. Граф G называется связным, если любые две его вершины связаны. В противном случае G не связен, а каждый из составляющих его подграфов G₁, G₂, …, G _l называется компонентой связности. Из определения связности следует, что в связном графе G вершина x_i связана сама с собой; если x_i связана c x_j, то x_j связана c x_i; если x_i связана c x_j, а x_j связана c x_k, то и x_i связана c x_k (x_i, x_j, x_k Î X).

Следовательно, отношение связности является отношением эквивалентности. В этом случае множество вершин Х графа G = (X, U), который моделирует любой объект, можно разбить на непересекающиеся классы G _i, причем ребра графа будут соединять только вершины внутри этих классов. Таким образом, получим разбиение графа G на связные подграфы (компоненты связности). Например, графы, изображенные на рис. 15.14, связные, а граф на рис. 15.25 состоит из четырех компонентов связности G₁ ─ G₄, т.е. не связен. Заметим, что связный граф состоит из единственной компоненты связности. Если граф имеет несколько компонент связности, то он не связен, так как вершины из разных компонент связности нельзя соединить маршрутом.

Рис. 15.25. Пример несвязного графа

Очевидно, что число ребер в связном графе

                                            n – 1 £ m £ n (n – 1)/2.                      (1.5)

Теорема 15.1. Пусть G – простой граф (см. стр. 10) с n вершинами и k компонентами. Тогда число m его ребер удовлетворяет неравенствам

                                        n – k £ m £ (n - k)(n - k + 1)/2.             (1.6)

Следствие 15.1. Любой простой граф с n вершинами и более чем (n – 1)(n – 2)/2 ребрами связен.

При конструировании систем часто надо знать, какое наименьшее число связей необходимо удалить из схемы, чтобы она перестала быть связной. Если вершины связного графа G = (X, U) разбить на 2 подмножества X’ и X’’, где X’’, X’ Ì X, X’’ = X \ X’, X’ È X’’ = X, то подмножество ребер U’ Ì U, у которых одни концевые вершины принадлежат X’, а другие X’’, называют разрезом графа G. Подграф G’ = (X, U\U’), полученный из G удалением ребер разреза, будет несвязанным графом, состоящим, по крайней мере, из двух компонент связности. Множество ребер U’’ Ì U, удаление которых дает несвязный подграф G’ = (X, U \ U’’) и не существует подмножества U’ÌU’’, такого, что G’’ = (X, U \ U’), несвязен, называют правильным разрезом. Из определения следует, что правильный разрез разбивает G точно на две компоненты связности. В этом случае разрез будет определяться как объединение правильных разрезов. На рис. 15.26,а показан пример разреза в графе G = (X, U). Разрез показан пунктирной линией.

                

              а                                                                       б

Рис. 15.26. Пример разреза в графе (а) и наличия точки сочленения (б)

Правильными разрезами будут следующие подмножества ребер: U₁ = {(x ₃, x ₆), (x ₄, x ₆), (x ₄, x ₇)}, U₂ = {(x ₄, x ₁₀), (x ₅, x ₁₀)}, U₃ = {(x ₅, x ₁₂)}, U₄ = {(x ₅, x ₁₅)}, а разрез U = U₁ È U₂ È U₃ È U₄. Заметим, что разрез в графе всегда существует. Тривиальными разрезами G являются U’ = U и U’ = Æ. Если разрез состоит из одного ребра u_i Î U, то u_i называется перешейком или мостом.

Точкой сочленения называется вершина графа, после удаления которой граф распадается на связные компоненты. Например, в графе G на рис. 15.26, б вершина 3 является точкой сочленения.

Неразделимый граф ─ это связный, непустой, не имеющий точек сочленения граф. Блок графа ─ это его максимальный неразделимый подграф. Если G ─ неразделимый граф, то он часто сам называется блоком. Так, на рис. 15.27 приведен пример графа G, имеющего две точки сочленения x ₅ и x _6, удаление которых разбивает граф G на 4 блока (рис. 15.28).

Граф блоков B(G) ─ это граф, в котором вершины ─ блоки и две вершины смежны, если соответствующие блоки имеют общую точку сочленения.

Вершинная связность H = H(G) в G – это наименьшее число вершин, удаление которых приводит к несвязному графу. H(G) в несвязном графе равна нулю. Связность в графе с точкой сочленения равна 1.

Рис. 15.27. Граф G        Рис. 15.28. Блоки графа G

Реберная связность l = l(G) – это наименьшее число ребер, удаление которых приводит к несвязному или тривиальному графу.

Для любого графа:

                                        H(G) £ l(G) £ r _min (G),                         (15.7)

где r _min (G) ─ наименьшая степень графа.

Граф G называется n-связным, если H(G) ³ n и n-реберносвязным, если l(G) ³ n.

Теорема 15.2 (Дирак). Если граф G n-связен, n ³ 2, то любое множество, содержащее n вершин графа G, принадлежит простому циклу.

Теорема 15.3. Граф 3 ─ связен тогда и только тогда, когда он или совпадает с колесом, или получается из колеса с помощью двух типов операций:

1) добавление нового ребра;

2) замена вершины V с r (V), по крайней мере, на две смежные вершины V’, V’’, где каждая вершина, которая была смежна с V, соединяется точно с одной из V’, V’’ так, чтобы в полученном графе r (V’) ³ 3 и r (V’’) ³ 3.

ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ

Пример 1. Пусть задан граф G, показанный на рис. 15.23. Подсчитать количество маршрутов длиной 3 в данном графе.

Решение: Запишем матрицу смежности графа G:

.

Как уже было показано ранее, чтобы найти число маршрутов длиной 2, в заданном графе необходимо возвести его матрицу смежности в квадрат. Алгебраическое произведение матриц определяется по формуле

r ² _ij = a_ik b_ki,

где r ² _ij ─ элемент матрицы R².

Вычислив, таким образом, значения всех элементов, мы придем в итоге к следующей матрице:

.

Для того, чтобы определить количество маршрутов длиной 3 в исходном графе, необходимо полученную на первом шаге матрицу R² умножить на R. Например,

r ³_1,2 = r _1,1 r ²_1,2 + r _1,2 r ²_2,2 + r _1,3 r ²_3,2 + r _1,4 r ²_4,2 = 0*0 + 1*2 + 2*3 + 0*0 = 4.

Используя вышеуказанную формулу умножения матриц, получим:

.

Из полученной матрицы R³ следует, что в исходном графе между вершинами, например, x ₁ и x ₂, существует 4 маршрута длиной 3: S₁ = (x ₁, x ₂)(x ₂, x ₁)(x ₁, x ₂); S₂ = (x ₁, x ₂)(x ₂, x ₄)(x ₄, x ₂); S₃ = (x ₁, x ₃)(x ₃, x ₁)(x ₁, x ₂); S₄ = (x ₁, x ₃)(x ₃, x ₄)(x ₄, x ₂).

Пример 2. Для графа, изображенного на рис. 15.29, привести примеры маршрута, цепи, цикла, простой цепи и простого цикла.

Рис. 15.29. Пример графа G

Ответ: Маршрутом в графе является любая конечная последовательность ребер, причем маршрут может проходить через одну и ту же вершину или ребро любое число раз. Тогда в качестве маршрута можно принять такую конечную последовательность: S = (x ₁, x ₂), (x ₂, x ₆), (x ₆ ─ x ₂), (x ₂ ─ x ₇), (x ₇ ─ x ₆), (x ₆ ─ x ₂). Цепью называют маршрут, не имеющий повторяющихся ребер. Таким образом, последовательность S = (x ₁, x ₂), (x ₂, x ₄), (x ₄, x ₆), (x ₆, x ₂), (x ₂, x ₇) можно считать цепью. Цикл представляет собой замкнутую цепь, т. е. цепь, у которой первая и последняя вершины совпадают. Тогда последовательность C = (x ₁, x ₅), (x ₅, x ₃), (x ₃, x ₁), (x ₁, x ₈), (x ₈, x ₅), (x ₅, x ₁) является циклом. При это, как мы видим, цепь и цикл могут проходить несколько раз через одну и ту же вершину. Простая цепь (цикл) не может включать в себя ни повторяющихся ребер, ни вершин. Примером простой цепи может служить последовательность S = (x ₁, x ₂), (x ₂, x ₄), (x ₄, x ₆), (x ₆, x ₈), (x ₈, x ₃); а простой цикл C = (x ₁, x ₅), (x ₅, x ₃), (x ₃, x ₁).

Пример 3. Для графа, заданного на рис. 15.30 привести пример разреза, правильного разреза.

Ответ: Правильными разрезами будут: U₁ = {(x ₃, x ₆), (x ₄, x ₆), (x ₄, x ₇); U₂ = {(x ₄, x ₁₀), (x ₅, x ₁₀)}; U₃ = {(x ₅, x ₁₂)}; U₄ = {(x ₅, x ₁₅)}. А разрез U определяется как их объединение: U = U₁ È U₂ È U₃ È U₄.

Рис. 15.30. Пример графа G

 

ВОПРОСЫ ДЛЯ САМОКОНТРОЛЯ

1. Что из себя представляет маршрут в графе?

2. Как определяется длина маршрута?

3. Что такое маршрут в графе. Как определяется длина маршрута?

4. Дайте определение цепи, цикла, простого цикла и простой цепи в графе.

5. Какой граф называется связным?

6. Что такое компонента связности?

7. Что такое блок графа?

8. Дайте определение разреза, правильного разреза графа. Приведите примеры.

9. Дайте определение вершинной связности. Приведите примеры.

10. Дайте определение реберной связности. Приведите примеры.