Уч.пособие-по-ОДМ-2012

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

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

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

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

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

171

Пример 9.13.

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

172

• Сумма элементов любого столбца равна степени соответству-

173

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

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

Пример 9.14.

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

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

174

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

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

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

графа G = < V, E > (обозначается G1 4 G), если V1 V, E1 E.

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 называется конечная последова-

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

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

176

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

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

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

рут из вершины vi в вершину vj, тогда существует и простая соединяющая их цепь.

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

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

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

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

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

177

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

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

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

178

Пример 9.20.

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

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

179

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

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

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

тогда, когда в нем отсутствуют циклы нечетной длины.

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

Пример 9.24.

180