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

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

Пример: (х₁: (1, 2), х₂: (1, 2), х₃: (1, 2), х₄: (1, 2), х₅: (1, 2), х₆: (1, 2), х₇: (1, 2)).

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

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

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

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

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

Пример:

– полный граф из 4-х вершин.

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

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

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

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

Пример:

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

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

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

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

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

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

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

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

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

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

Вывод:

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

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

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

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

Пример:

(полный граф, а следовательно регулярный)

(регулярный, но не полный)

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

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

Пример:

deg G₁ = deg G₂ = 3.

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

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

Пример:

(V₁ – висячая, V₆ - изолированная).

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

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

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

Пример:

(планарный граф)

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

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

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

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

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

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

Пусть 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 ребрами и с хотя бы одной тупиковой вершиной.

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

В пунктах (а) и (б) мы доказали, что равенство (*) справедливо для любого графа 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. Обозначим через a_i число ребер, принадлежащих грани i. Так как каждое ребро принадлежит границе не более двух граней, то . С другой стороны, при p ³ 3 граница каждого ребра имеет не менее трех ребер. Значит, для любого i, a_i ³ 3, то есть . Таким образом, мы получили, что , 3r ≤ 2q Þ 3(q – p + 2) ≤ 2q Þ q ≤ 3(p – 2), что и требовалось доказать.

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

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

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

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

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

Пример:

– эйлеровый граф – не эйлеровый граф

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

Пример:

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

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

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

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

– это не эйлеровый граф

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

Определение. Два графа: 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 называют изоморфизмом.

Пример:

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

j: (U₁ « W₂, U₂ « W₃, U₃ « W₄, U₄ « W₁) – изоморфизм

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

Инварианты

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

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

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

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

Пример:

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

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

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

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

Пример:

p = 1

p = 2

p = 3

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

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

– не изоморфны

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

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

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

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

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

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

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

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

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

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

(Лекция 7)

Деревья. Лес

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

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

Пример:

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

Пример:

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

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

В дереве с 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.

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

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

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

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

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

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