В) Матрица векторов смежности

Наряду с заданием графа матрицей смежности и инцидентности можно воспользоваться представлением графа матрицей, элементы которой непосредственно соответствуют индексам поименованных вершин этого графа. В такой матрице i-ая строка содержит вектор, компонентами которого являются все вершины, смежные с Vi. Порядок элементов в таком векторе (векторе смежности) обычно определяется порядков, в котором представлены ребра в графе.

Пример: (х1: (1, 2), х2: (1, 2), х3: (1, 2), х4: (1, 2), х5: (1, 2), х6: (1, 2), х7: (1, 2)). в) Матрица векторов смежности - student2.ru

Заметим, что:

1) Размер этой матрицы никогда не превышает p ´ d, где d = в) Матрица векторов смежности - student2.ru .

2) Векторы смежности особенно удобно представляют граф, когда задача может быть решена за небольшое число просмотров ребра в матрице G.

Полный граф. Дополнение графа

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

Пример:

в) Матрица векторов смежности - student2.ru – полный граф из 4-х вершин.

Заметим, что:

1) В полном графе каждая его вершина инцидентна одному и тому же числу его ребер.

2) Для задания полного графа достаточно знать число его вершин.

3) Неполный граф можно преобразовать в полный, добавив недостающее число ребер.

Пример:

в) Матрица векторов смежности - student2.ru

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

Определение. Две вершины в графе дополнения к G смежны тогда и только тогда, когда они не смежны в графе G.

Характеристики вершин

Определение. Степень вершины – число ребер, инцидентных данной вершине.

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

Теорема (Исторически первая теорема теории графов, Основная теорема теории графов, Теорема Эйлера).

Сумма степеней вершин графа G равна удвоенному числу ребер ( в) Матрица векторов смежности - student2.ru = 2q).

(Утверждение является достаточным доказательством).

Следствие. В любом графе число вершин с нечетными степенями четный.

Доказательство: Пусть V1 Í V – множество вершин с нечетными степенями, V2 Í V – множество вершин с нечетными степенями. Множество всех вершин рассматриваемого графа: V, V =V1 È V2, V1 Ç V2 = Æ. По Теореме Эйлера в) Матрица векторов смежности - student2.ru = 2q – четное, в) Матрица векторов смежности - student2.ru = 2k – четное. Отсюда: в) Матрица векторов смежности - student2.ru = 2p – 2k – четная.

Вывод:

1) Так как степень каждой вершины нечетная, а сумма четная, то количество вершин с нечетными степенями (V1) – четное.

2) Степень вершины: 0 ≤ deg V ≤ p – 1, для любой вершины V.

Определение. Пусть в) Матрица векторов смежности - student2.ru , D(G) = в) Матрица векторов смежности - student2.ru . Если в графе G, d(G) = D(G) = r, то все вершины имеют одинаковую степень и такой граф называется регулярным или однородным степени r, то есть deg G = r.

В полном графе каждая пара вершин смежна. Отсюда следует, что любой полный граф является регулярным с p вершинами, тогда deg Kp = p – 1. Но далеко не каждый регулярный граф является полным.

Пример:

в) Матрица векторов смежности - student2.ru (полный граф, а следовательно регулярный)

в) Матрица векторов смежности - student2.ru (регулярный, но не полный)

Регулярный граф степени ноль совсем не имеет ребер.

Определение. Если граф G – регулярный граф степени 3, то он называется кубическим.

Пример:

в) Матрица векторов смежности - student2.ru deg G1 = deg G2 = 3.

Каждый кубический граф имеет кубическое число вершин.

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

Пример:

в) Матрица векторов смежности - student2.ru (V1 – висячая, V6 - изолированная).

Планарный граф

Определение. Изображение графа называется правильным (плоским), если линии, изображающие ребра, не пересекаются.

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

Пример:

в) Матрица векторов смежности - student2.ru (планарный граф)

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

в) Матрица векторов смежности - student2.ru

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

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

Пример: f5 – внешняя грань.

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

Теорема (о количестве граней связанного планарного графа).

Пусть G – связанный планарный граф с p вершинами и q ребрами. Число граней в любом его плоском изображении равно r = q – p + 2 (Формула Эйлера).

(Лекция 6)

Доказательство (методом математической индукции по числу ребер):

1) q = 0 Þ p = 1 Þ r = 1 = 0 – 1 + 2 Þ (*) верно при q = 0

2) Допустим формула (*) справедлива для графа с q-1 ребром.

а) Пусть в графе с q ребрами есть хотя бы одна тупиковая вершина. Удалим эту вершину. Удаляется и ребро, соединенное с этой вершиной. Þ Получим граф G’ с q’ = q – 1 ребрами и p’ = p – 1 вершинами. Тогда число граней r’ = r, но при этом r’ = q’ – p’ + 2 – верна по допущению. Значит r = q – 1 – (p – 1) + 2 = q – p +2 Þ (*) истинна и для графа G c q ребрами и с хотя бы одной тупиковой вершиной.

в) Матрица векторов смежности - student2.ru

б) Пусть в графе G с q ребрами нет ни одной тупиковой вершина, а значит – каждая вершина имеет как минимум степень 2. По свойству 3 путей и циклов в этом графе есть цикл. Пусть (a, b) – ребро из этого цикла. На диаграмме, изображающей граф G, ребро (a, b) лежит на границе двух областей (f1 и f2). Удалим ребро (a, b). Получим граф G’’, у которого p’’ = p, q’’ = q – 1, r’’ = r – 1. По допущению справедлива формула r’’ = q’’ – p’’ + 2 Þ r – 1 = q – 1 – p + 2, то есть (*) верно и для графа G с q ребрами, у которого нет тупиковой вершины.

в) Матрица векторов смежности - student2.ru

В пунктах (а) и (б) мы доказали, что равенство (*) справедливо для любого графа G.

Вывод: Так как выполнено оба условия обобщенного принципа математической индукции, то (*) выполняется для любого графа G.

Следствие:

1) Если связанный планарный граф G имеет p вершин (p ³ 3) и q ребер, то q ≤ 3 × (p – 2).

2) Если граф G к тому же еще и содержит цикл длины 3, тогда q ≤ 2 × (p – 2).

Доказательство:

1) Пусть r – число граней в плоском изображении графа G. Тогда r = q – p +2. Занумеруем графы натуральными числами от 1 до n. Обозначим через ai число ребер, принадлежащих грани i. Так как каждое ребро принадлежит границе не более двух граней, то в) Матрица векторов смежности - student2.ru . С другой стороны, при p ³ 3 граница каждого ребра имеет не менее трех ребер. Значит, для любого i, ai ³ 3, то есть в) Матрица векторов смежности - student2.ru . Таким образом, мы получили, что в) Матрица векторов смежности - student2.ru , 3r ≤ 2q Þ 3(q – p + 2) ≤ 2q Þ q ≤ 3(p – 2), что и требовалось доказать.

в) Матрица векторов смежности - student2.ru

2) Если граф G не содержит цикл длины 3, то граница всякой грани имеет не более 4 ребер (то есть для любого i, ai ³ 4) Þ в) Матрица векторов смежности - student2.ru . Таким образом, 4r ≤ 2q Þ 4(q – p + 2) ≤ 2q Þ q ≤ 2(p – 2), что и требовалось доказать.

Пример: Является ли планарным граф K5? Þ p = 5, q = 10. q ≤ 3(p – 2) Þ 10 ≤ 3 × 3 (неверно) Þ Следовательно, граф K5 не планарный.

Эйлеровы графы

Определение. Цикл, содержащий все ребра графа, называется эйлеровым циклом.

Определение. Граф, содержащий эйлеровы циклы, называется эйлеровым графом.

Пример:

в) Матрица векторов смежности - student2.ru – эйлеровый граф в) Матрица векторов смежности - student2.ru – не эйлеровый граф

Определение. Эйлеровы графы – граф, которые можно изобразить одним росчерком пера, причем процесс такого изображения должен начинаться и заканчиваться в одной и той же точке.

Пример: в) Матрица векторов смежности - student2.ru

Теорема Эйлера об эйлеровых графах (критерий эйлеровости графа)

Конечные неориентированный граф G является эйлеровым, тогда и только тогда, когда он связный и степени всех его вершин четные.

Доказательство: См. [2], стр. 106 – 107.

Задача о Кенигсбергских мостах

в) Матрица векторов смежности - student2.ru – это не эйлеровый граф

Изоморфизм графов

Определение. Два графа: G и H – изоморфные (G @ H), если между множествами их вершин существует взаимно-однозначное отображение, сохраняющее смежность.

Определение. Два графа G = (V, X) и H = (W, Y) называются изоморфными, если существует взаимно-однозначное отображение j: V ® W, сохраняющее смежность, такое, что для пары u, u Í V (j(u), j(u)) Í Y Û (u, u) Í X. В этом случае отображение j называют изоморфизмом.

Пример:

в) Матрица векторов смежности - student2.ru

j: (Ui « Wi), i = 1, 2, 3, 4 – не изоморфизм.

j: (U1 « W2, U2 « W3, U3 « W4, U4 « W1) – изоморфизм

Определение. Граф G, в котором выделена некоторая вершина V, называется корневым, а эта вершина – корень графа G. При изоморфизме корневых графов корню должен соответствовать корень.

Инварианты

Задача. Выяснить, изоморфны ли графы, можно перебором всех взаимно-однозначных отображений множества вершин одного из них в множество вершин другого. Однако таких отображений имеется p!. Для более простой проверки будем пользоваться инвариантами, то есть такими характеристиками графов, значения которых сохраняются при изоморфизмах.

Чаще всего инвариант графа G это число или последовательность чисел, связанных с графом G.
Простейшими инвариантами являются: число вершин, число ребер, спектр (набор) степеней вершин, длина циклов, число компонент связности.

Определение. Компонентой связности графа G называется его максимальный связный подграф.

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

Пример:

в) Матрица векторов смежности - student2.ru

5 компонент связности

Таким образом, несвязный граф имеет как минимум 2 вершины.

Полный набор инвариантности (код графа)

Определяет граф с точностью до изоморфизма, в частности, число вершин и число ребер графа образует полный набор инвариантов для всех графов с числом вершин не больше трех.

Пример:

p = 1 в) Матрица векторов смежности - student2.ru

p = 2 в) Матрица векторов смежности - student2.ru

p = 3 в) Матрица векторов смежности - student2.ru

Множество вершин – полный инвариант.

Пример: p = 4, q = 3.

в) Матрица векторов смежности - student2.ru – не изоморфны

В настоящее время не известно ни одной нетривиальной полной системы инвариантов для графов.

Алгоритм решения задач изоморфизма:

1. Попытаться доказать, что графы не изоморфны. Для этого составляется список различных инвариантов в порядке, определяемом сложностью инвариантов. Затем последовательно начинают сравнивать значения инвариантов.

2. Если графы не изоморфны, то нужно установить изоморфизм.

Примечание. Будет доказано, что графы не изоморфны, если будут указаны несовпадающие инварианты.

Число графов с p вершинами (g(p))

Теорема (О числе графов с p вершинами):

в) Матрица векторов смежности - student2.ru

Доказательство: Каждый граф со множество вершин Р задается некоторым подмножеством множества всех неупорядоченных пар элементов V. Всего имеется возможностей составить пары в) Матрица векторов смежности - student2.ru . По Теореме о мощности всех подмножеств данного множества всего имеется в) Матрица векторов смежности - student2.ru графов.

в) Матрица векторов смежности - student2.ru

С учетом изоморфизма, то есть число графов не изоморфных между собой и имеющих p вершин меньше g(p).

Пример: g(3) = 23 = 8

(Лекция 7)

Деревья. Лес

Определение. Граф называется ациклическим, если в нем нет циклов.

Определение. Деревом называется связный ациклический граф.

Пример:

в) Матрица векторов смежности - student2.ru

Определение. Каждый граф, не содержащий циклов, называется лесом.

Пример:

в) Матрица векторов смежности - student2.ru

Вывод: Таким образом компонентами леса являются деревья.

Теорема (О количестве ребер дерева)

В дереве с p вершинами число ребер равно p – 1, то есть q = p – 1 (*).

Доказательство (методом математической индукции):

1) p = 1 Þ q = 0 Þ (*) истинно при p = 1.

2) Допустим, что равенство (*) верно и для графа с p–1 вершиной, то есть допустим, что q = p – 2. Докажем что (*) справедлива и для дерева с p вершинами. Поскольку дерево – ациклический граф, то в нем есть хотя бы одна вершина степени p = 1. Удалим ее. Получится граф с p–1 вершиной. По допущению, у такого дерева p – 2 ребра. Рассматриваемый граф с p вершинами отличается от графа с p – 1 вершиной наличием лишнего ребра. Значит, у графа с p вершинами ребер на единицу больше, чем p – 2, то есть q = p – 1.

Вывод: Так как выполнено оба условия обобщенного принципа математической индукции, то (*) выполняется для любого дерева.

Пример дерева с выделенным корнем:

в) Матрица векторов смежности - student2.ru

Для дерева достаточно создать одномерный массив. Из каждой вершины только одно ребро ведет к корню. Будем двигаться по дереву так, чтобы ребро было справа. При движении вдоль ребра в одном направлении приписываем этому ребру ноль, а в обратном направлении – единицу.

в) Матрица векторов смежности - student2.ru

Выпишем все нули и единицы: 000010110010111010011101

При этом число единиц и нулей будут равны между собой и равны числу ребер.

Код дерева задает его построение однозначно. С помощью кода дерево удобно задавать в ЭВМ.

Наши рекомендации