Дискретная математика

Для ориентированного графа первым в упорядоченной паре стоит вершина, являющаяся началом ребра, а вторым - конец ребра. Дуги перечисляются в круглых скобках.

При изображении графов, заданных списком ребер, сначала определяют множество вершин. Графы, задаваемые списком ребер, при изображении различаются в зависимости от расположения вершин на рисунке. При этом все изображенные по одному списку графы являются изоморфными.

Чаще всего вершины на рисунке располагают по кругу и соединяют соответствующими ребрами из списка.

Для удобства изображения граф можно нарисовать так, чтобы количество пересекающихся ребер в нем было минимальным.

Пример 9.12.

а)

G1 = {{v1, v2}, {v1, v3}, {v1, v4}, {v2, v3},

{v2, v4}, {v3, v4}, {v4, v5}}

- неориентированный граф. Его изображение:

б) Граф

G2 = {(v1, v2), (v1, v5), (v2, v3), {v3, v4},

{v3, v5}, (v3, v1), {v4, v5}}

- ориентированный:

171

4). Матрица инцидентности.

Пусть V = {v1, v2, . . . , vn} - множество вершин графа G; E = {e1, e2, . . . , em} - множество его ребер.

Тогда граф можно задать матрицей Am×n = {aij}, называемой

матрицей инцидентности. Am×n имеет m строк и n столбцов; столбцы соответствуют вершинам графа, строки - ребрам.

Пример 9.13.

a) G1 = {V1, E1}, где V1 = {v1, v2, v3, v4, v5, v6},

E1 = {e1, e2, e3, e4, e5, e6, e7, e8, e9, e10, e11}.

172

Свойство матрицы инцидентности неориентированного графа:

•Сумма элементов любого столбца равна степени соответствующей вершины, то есть

∑

deg(vj) = aij

i

.

173

5). Матрица смежности.

Определение 9.13. Матрицей смежности неориентированного графа G = < V, E > называется матрица An×n = (aij), где aij - число ребер, соединяющих вершины i и j; n - количество вершин в графе.

Пример 9.14.

Для графа G1 из предыдущего примера матрица смежности равна

Свойства матрицы смежности неориентированного графа:

•Все элементы матрицы - неотрицательные числа.

•Матрица является симметрической, то есть AT = A.

•Сумма элементов i-той строки (столбца) равна степени соот-

ветствующей вершины :

∑

aij = deg(vi)

j

∑

aij = deg(vj)

i

Матрицы инцидентности и смежности задают единственный с точностью до изоморфизма граф.

174

9.3Графы специального вида

В этом разделе мы будем рассматривать только простые графы (то есть графы без кратных ребер и петель).

Определение 9.14. Граф G1 = < V1, E1 > называется подграфом

графа G = < V, E > (обозначается G1 4 G), если V1 V, E1 E. Каждая вершина подграфа G1 является вершиной исходного графа

G, каждое ребро G1 - ребро G.

Пример 9.15. Графы G1, G2 и G3 являются подграфами графа G.

175

Определение 9.15. Пусть задан неориентированный граф

G= < V, E >, V = { v1, v2, . . . , vk }, E = { e1, e2, . . . , el }.

Маршрутом из вершины vi в вершину vj называется конечная по-

следовательность ребер {vi, vi1 }, {vi1 , vi2 }, . . . , {vis−1 , vis }, {vis , vj}. Количество ребер в маршруте называется его длиной.

Вершину vi называют начальной вершиной маршрута, vj - его

конечной вершиной.

Определение 9.16. Пусть задан ориентированный граф

G = < V, E >, V = { v1, v2, . . . , vk }, E = { e1, e2, . . . , el }.

Путем из вершины vi в вершину vj называется конечная последова-

тельность ребер (vi, vi1 ), (vi1 , vi2 ), . . . , (vis−1 , vis ), (vis , vj). Количество ребер в пути называется его длиной.

Вершину vi называют начальной вершиной пути, vj - его конечной вершиной.

Путь или маршрут часто указывают, перечисляя его вершины:

vi → vi1 → vi2 → · · · → vis−1 → vis → vj.

Каждые 2 последовательных ребра маршрута {vik−1 , vik } и {vik , vik+1 } имеют общую вершину vik и являются смежными.

Пример 9.16. Последовательности ребер

являются маршрутами из v1 в v5 в графе G из примера 9.15. v1 - начальная вершина маршрута, v5 - его конечная вершина.

Определение 9.17. Тривиальным называется маршрут длины 0.

176

Определение 9.18. Маршрут называется цепью, если все его ребра различны; простой цепью - если все его вершины различны, за исключением, быть может, начальной и конечной.

Если начальная и конечная вершины цепи совпадают, цепь называют замкнутой.

Циклом в графе называют замкнутую цепь, содержащую по крайней мере одно ребро; простым циклом - цикл, в котором все вершины, за исключением начальной и конечной, различны.

Пример 9.17. Маршруты из п. а), б), в) предыдущего примера - цепи, причем а) и б) - простые цепи.

г) {v1, v4}, {v4, v2}, {v2, v1}, {v1, v4}, {v4, v5} - пример маршрута, не являющегося цепью.

д) Последовательность ребер {v1, v4}, {v4, v5}, {v5, v1} является простым циклом.

Теорема 9.3. Пусть G = < V, E > - граф. Если существует маршрут из вершины vi в вершину vj, тогда существует и простая соединяющая их цепь.

Доказательство. Пусть маршрут из vi в vj не является простой цепью. Тогда существует по крайней мере одна вершина vm, встречающаяся в нем не менее двух раз, и маршрут имеет вид

vi → vi1 → . . . → vm → vm+1 → . . . → vm → . . . → vj.

Удалив из маршрута последовательность ребер vm+1 → . . . → vm, снова получим маршрут из vi в vj.

Если при этом он не будет простой цепью, процедуру можно повторить. Так как число ребер в конечном маршруте конечно, процесс удаления ребер конечен.

В результате получим простую цепь из vi в vj.

Определение 9.19.

Граф G называется связным, если имеется маршрут между любыми его двумя различными вершинами.

177

Пример 9.18. а) G1 - связный граф.

б) Граф G2 - не является связным, так как не существует маршрута, например, из v2 в v4, из v1 в v6 и так далее.

Теорема 9.4. Граф G является связным тогда и только тогда, когда между любыми двумя его вершинами существует простая цепь.

Доказательство. непосредственно следует из теоремы 9.3 и определения 9.19 связного графа.

Определение 9.20. Подграф G1 графа G называется компонентой (компонентой связности), если G1 - максимальный связный подграф графа G.

Пример 9.19.

имеет три компоненты связности.

Определение 9.21. Пустым (вполне несвязным) называется граф, в котором нет ребер.

Пустой граф с n вершинами обычно обозначается Nn.

178

Пример 9.20.

Замечание 9.3. У пустого графа все вершины изолированы.

Определение 9.22. Полным называется граф, любые две вершины которого смежны.

Обозначение полного графа с n вершинами Kn.

Свойство полного графа с n вершинами Kn:

Определение 9.23. Двудольным называется граф, множество вершин которого можно разбить на два непересекающихся подмножества V1 и V2 ( на две доли) и при этом каждое ребро графа соединяет какую-либо вершину из V1 с какой-либо вершиной из V2, но никакие две вершины из одного множества не являются смежными.

Заметим, что вершины двудольного графа можно "раскрасить" (каждой вершине приписать некоторый цвет) в два цвета так, что вершины из одного подмножества (доли) будут окрашены в один цвет, а каждое ребро будет иметь концы разного цвета.

179

Определение 9.24. Полным двудольным графом называется двудольный граф, в котором каждая вершина из V1 смежна с каждой вершиной из V2.

Полный двудольный граф, у которого |V1| = n, |V2| = m (n и m - количество вершин в соответствующей доле), обозначается через Kn;m.

Очевидно, что в графе Kn;m количество ребер равно n · m.

Теорема 9.5 (Д.Кёнинг). Граф является двудольным тогда и только тогда, когда в нем отсутствуют циклы нечетной длины.

Определение 9.25. Звёздным называют граф K1;n.

Пример 9.24.

180