Вопросы для самоконтроля

1. Что такое граф? Приведите пример. Назовите известные вам типы графов.

2. В чем состоит различие между ориентированными и неориентированными графами?

3. Опишите известные вам способы задания графов.

4. Что называется подграфом и суграфом графа?

5. Что называется дополнением графа?

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

7. Какие операции могут выполняться над графами?

8. Что такое мультиграф и как определяется его мультичисло?

9. Дайте определение регулярного графа.

10. Дайте определение нечеткого графа. В чем состоит отличие нечеткого неориентированного графа первого и второго рода?

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

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}.

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

Маршрутом в графе 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,3r_3,1 + r_2,3r_3,2 + r_3,3r_3,3 + r_4,3r_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

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

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

H(G)  (G)  _min(G), (15.7)

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

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

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

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

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

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