Теория графов

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

1. Основные определения теории графов

Многие задачи сводятся к рассмотрению совокупности объектов, существенные свойства которых описываются связями между ними. Например, глядя на карту автомобильных дорог, можно интересоваться только тем имеется ли связь между некоторыми населёнными пунктами, отвлекаясь от конфигурации и качества дорог, расстояний и других подробностей. При изучении электрических цепей на первый план может выступать характер соединений различных её компонентов - резисторов, конденсаторов, источников и т.п. Органические молекулы образуют структуры, характерными свойствами которых являются связи между атомами.

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

Определение. Множество, вершин V, связи между которыми определены множеством рёбер Е, называют графом и обозначают G=(V, E).

Слово граф происходит от латинского слова «графио» - пишу. Типичными графами являются блок-схемы программ для ЭВМ, схемы авиалиний, схемы-маршруты движений автобусов.

Первая работа по теории графа была опубликована 20-летием швейцарским математиком Леонардом Эйлером в 1736 г., когда он работал в Российской Академии наук. Она содержала решение задачи о кенигсбергских мостах (рис. 1)

Рисунок 1

и имела следующее содержание: река Прегель делит г. Кенигсберг на 4 части: А, В, С, D, связанные между собой 7 мостами. Требуется определить можно ли выйдя из какой-либо части города пройти по всем мостам по 1 разу и вернуться в исходную часть города. Согласно условию задачи не имеет значения, как проходит путь по части суши А, В, С, D на которых расположен г. Кенигсберг (ныне Калининград), поэтому их можно представить вершинами. А так как связи между этими частями осуществляется только через 7 мостов, то каждый из них изображается ребром, соединяющим соответствующие вершины. В результате получаем следующий граф.

Рисунок 2

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

На рис. 3 а) изображен граф, в котором существуют пары вершин, соединенные более чем одним ребром. Различные ребра, соединяющие две данные вершины, называются кратными. Граф, изображенный на рис. 3 6), содержит ребра, соединяющие вершину саму с собой. Такие ребра называют петлями.

Рисунок 3

Более точно, графом называют тройку (V, Е, ц), где V, Е - конечные множества, V ? Ш и ц - отображение из Е в V ⁽²⁾ U V. Если ц(е) = {u, v}, где и ?v, то говорят, что ребро е соединяет вершины и, v. В этом случае будем писать е = uv. Если ц(е) = w, то ребро е называют петлей в вершине n. В этом случае будем также писать е = ии и говорить, что е соединяет вершину w саму с собой.

Записывая произвольный граф, мы часто будем опускать ц и представлять граф в виде G - (V, Е).

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

Отметим, что обыкновенный граф - это граф без петель и кратных ребер.

Граф G, имеющий п вершин, часто называют п - графом; если, кроме того, G содержит т ребер, то G - (п, т) - граф.

Если е = uv - некоторое ребро данного графа, то вершины и, v называются смежными; говорят также, что и, v - концевые вершины ребра е. Ребро е и вершина v инцидентны, если v - концевая вершина для е. Ребра еиѓ называются смежными, если они имеют общую концевую вершину.

Пусть G₁ = (V₁, E₁), G₂ = (V₂, Е₂) - два графа. Биективное отображение: ш:V₁ > V₂ называется изоморфизмом G₁ на G₂, если для любых и, v €V₁ число ребер, соединяющих вершины ш(и) ш(v) в G₁, равно числу ребер, соединяющих ш(u) и ш(v) в G₂ (разумеется, при u = v число петель в вершине и равно числу петель в вершине ш(и)).

Отметим, что в случае обыкновенных графов изоморфизм - это биек-ция, сохраняющая отношение смежности; иными словами, изоморфизм ш характеризуется свойством: произвольные вершины и, v смежны в графе G1 тогда и только тогда, когда вершины ш(u), ш(v) смежны в графе G₂.

Графы G₁ и G₂ изоморфны (G₁= G₂), если существует изоморфизм ш на G₂. На рис. 4 приведены диаграммы двух изоморфных графов. Действительно, отображение ш, определенное правилом ш(u_i) = V_i, (1 ? i ? 6), очевидно, является изоморфизмом.

Отношение «быть изоморфными» на множестве всех графов, очевидно, является отношением эквивалентности. Таким образом, множество всех графов разбивается на классы попарно изоморфных графов. Заметим, что диаграмма задает граф с точностью до изоморфизма. Степенью вершины v называется число ребер, инцидентных этой вершине, причем каждая петля учитывается дважды. Степень вершины v обозначается через deg_Gv или просто через degv. Ясно, что в обыкновенном графе степень вершины v равна количеству вершин, смежных с v. Окружением N(v) вершины v называется множество всех вершин, смежных с v.

Рисунок 4

Если degv=0, то вершина v называется изолированной, а если degv=l, то - висячей. Ребро е, инцидентное висячей вершине, также называют висячим.

Лемма 1 (о рукопожатиях). Пусть G - произвольный граф. Тогда



Доказательство. При подсчете суммы степеней произвольное ребро

е = uw внесет свой вклад, равный единице, как в deg u, так и в deg w, причем петля будет учитываться дважды.

Следствие. Произвольный граф содержит четное число вершин нечетной степени.

Доказательство. Пусть V₀ и V₁ - соответственно множества вершин четной и нечетной степени. Тогда

Ясно, что первое слагаемое четно. Поэтому второе слагаемое также четно. Так как во второй сумме все слагаемые нечетны, их число четно. Следовательно, множество V₁ содержит четное число вершин.

Будем называть граф одноэлементным, если он имеет единственную вершину. Граф G называется нулевым или вполне несвязным, если множество его ребер EG пусто. Нулевой n-граф будем обозначать через О_п. Диаграмма графа О₄. Ясно, что нулевой граф является обыкновенным графом.

Обыкновенный граф G называется полным графом, если любые его две различные вершины смежны. Для полного n-графа применяется обозначение К_п. Очевидно, степень каждой вершины в графе К_п равна п - 1. Поэтому из леммы о рукопожатиях следует, что число ребер в К_п равно

Граф G называют двудольным, если множество VG можно разбить на два непустых подмножества X и Y так, что любое ребро графа соединяет вершину из X с вершиной из Y. Множества X и Y - это доли двудольного графа G. Если любые вершины х € X и у € Y смежны и двудольный граф является обыкновенным графом, то G называют полным двудольным графом. Если |Х| = р,|Y| = q, то такой полный двудольный граф обозначают через K_p,_q.

Граф Н называется подграфом графа G, если VH С VG и ЕН С EG. В число подграфов графа G будем включать и пустой подграф Ш. Если

VH - VG, то подграф Н называется ?стовным подграфом. Редукция графа G - это такой его остовный подграф Н, что Н является обыкновенным графом с наибольшим возможным числом ребер.

Пусть U - подмножество из VG. Обозначим через D множество всех ребер е = uv € EG таких, что и, v € U. Граф G(U) = (U, D) называется подграфом, порожденным множеством вершин U.

Аналогично определяется подграф, порожденный заданным множеством ребер. Пусть D С EG. Обозначим через U множество всех вершин, являющихся концевыми для ребер из D. Тогда граф G(D) = (U, D) называют подграфом, порожденным множеством ребер D.

Пусть G - произвольный граф и H - его подграф. С каждой вершиной v и каждым ребром е можно связать подграфы Н - v, H-еиH + е.

Подграф Н - v получается из подграфа Н удалением вершины v и всех инцидентных этой вершине ребер. Отметим, что если v не лежит в подграфе Н, то Н - v = Н'.

Подграф Н - е получается из Н удалением ребра е. Здесь также Н - е = Н, если е не лежит в Н.

Подграф Н + е получается из Н добавлением ребра е и двух его концевых вершин. Если е лежит в H, то Н + е = Н.

Через Sub(G) будем обозначать множество всех подграфов графа G. Определим отношение ? на Sub(G), полагая Н₁ ? Н₂ для подграфов H₁ и Н₂ графа G тогда и только тогда, когда H₁ является подграфом в Н₂, т.е. когда VH₁ С VH₂ и EH₁ С ЕН₂. Очевидно, отношение ? есть частичный порядок на Sub(G). Будем говорить, что H₁ содержится в Н₂, если H₁?Н₂.

Пусть H₁ и Н₂ - произвольные подграфы графа G.



2. Маршруты, связность, циклы и разрезы

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

Первый маршрут проходит через последовательность вершин (V₁, V₂, V₃, V₂, V₃, V₅) и соединяет вершины V₁ и V₅; второй-через последовательность вершин (V₃, V₅, V₅, V₂, V₅) и соединяет вершины V₃, V₅.

Маршрут называется замкнутым, если он приводит в ту же вершину из которой он начался.

Маршрут, все ребра которого различны, называется цепью.

Пример. В выше приведенном примере (№1) маршрут (l₂, l₅, l₆) - цепь.

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

Пример В выше приведенном примере (№1) маршрут (1₁, l₂, l₅) - простая цепь.

* Замкнутая цепь называется циклом.

Пример В выше приведенном примере (№1) маршрут (1₂, l₃, l₄, l₅) - цикл.

* Простая цепь называется простым циклом.

Заметим, что цикл полностью определяется множеством своих ребер, поэтому часто под циклом мы будем понимать соответствующее ему множество ребер. Петля дает цикл длины 1, пара кратных ребер образует цикл длины 2. Циклы длины 3 называют обычно треугольниками.

Пример В выше приведенном примере (№1) маршрут (1₂, 1₄, l₅) - простой цикл.

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

* Граф, в котором имеется эйлеров цикл, называется элеровым графам.

Лемма1. Если степень каждой вершины конечного графа четна, то на графе существует хотя бы один простой цикл.

* Две вершины графа называются связанными, если существует маршрут соединяющий эти вершины.

* Граф, пара вершин которого связана, называется связанным графом.

Сильно связный граф

Рисунок 5

Теорема (Критерий эйлеровости графа)

Для того, чтобы конечный (связный) граф был эйлеровым, необходимо и достаточно, чтобы степени всех его вершин были четными числами,

* Связный граф называется квазиэйлеровым, если на нем, существует простая цепь, проходящая через все дуги графа

Теорема (Критерий квазиэйлеровости)

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

* Простой цикл, который проходит через все вершины графа, называют гамильтоновым.

Критерия гамильтонового цикла нет.

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

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

Маршрут, не содержащий повторяющихся вершин называется простым путем,

Замкнутый путь называется контуром

Простой замкнутый путь называется простым контуром.

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

Понятие цепи и цикла применимы и к ориентированным графам. При этом направления дуг не учитываются, т.е. по существу вместо орграфа рассматривают неориентированный соотнесенный ему граф.

Теорема 1.1. Каждый граф является дизъюнктным объединением своих компонент связности.

В дальнейшем граф, имеющий п вершин, т ребер и к компонент связности, будем называть (n, m, к) - графом.

Разрезающим множеством ребер графа называется множество ребер, удаление которого из графа приводит к увеличению числа компонент связности. Минимальное по включению разрезающее множество ребер графа называется его разрезом. Мост графа - это ребро, составляющее одноэлементный разрез. Иными словами, при удалении моста число компонент связности возрастает. На рис. 6, 7 показаны примеры разрезов в графах, причем на рис. 6 б) показан мост.

Рисунок 6

Рисунок 7

Замечание: при наличие моста в графе имеется, по крайней мере, две точки сочленения.

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

Пример



Неразделимый граф

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

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

Пример Из П₄

В₁

Блоки В₁, В₂, В₃ графа из П₄

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

Лемма 2. При удалении из графа моста число компонент связности увеличивается точно на единицу.

Доказательство. Пусть из графа удаляется мост е = uv. В графе G - е вершины и и v нельзя соединить простой цепью, иначе сохранится отношение связности и, следовательно, сохранится число компонент связности. Таким образом, вершины и и v лежат в разных компонентах связности графа G - е.

Пусть х - произвольная вершина графа G, для которой существует простая (х, v) - цепь (в силу леммы 1 это в точности те вершины, которые лежат в той же компоненте связности графа G, что и вершина v). Если в этой простой цепи не встречается ребро е, то вершины х и v лежат в одной компоненте связности графа G - е. Если в такой простой цепи встречается ребро е, то цепь обязательно имеет вид х>…>и >V.

Поэтому вершины х и и лежат в одной компоненте связности графа

G - е.

Итак, при удалении моста е точно одна компонента связности графа G, а именно, компонента, содержащая v, распадается на две компоненты связности графа G - е. ?

Лемма 3. При удалении из графа ребер его разреза число компонент связности увеличивается точно на единицу.

Доказательство. Пусть из графа G удаляется разрез {ei, е₂,…, e_t}. Можно считать, что t > 1. После удаления множества ребер {ei, е₂,…, e_t_i} число компонент связности сохраняется и ребро e_t становится мостом. Дальнейшее удаление ребра e_t в силу леммы 2 приводит к увеличению числа компонент связности ровно на единицу.

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

Лемма 4. Ребро графа является мостом тогда и только тогда, когда оно не содержится ни в одном цикле.

Доказательство. Пусть е = uv - мост. Если е содержится в некотором цикле, то существует простая (и, v) - цепь, не содержащая е. Следовательно, после удаления ребра е из графа отношение связности не изменится, что невозможно.

Обратно, пусть е = uv не является мостом. После удаления е из графа G вершины и и v будут лежать в одной компоненте связности графа G - е. В силу леммы 1 в графе G - е имеется простая (и, v;) - цепь. Добавляя к этой цепи ребро е, получим цикл графа G_: содержащий ребро е. ?

Из леммы 4 вытекает, что ациклические ребра - это в точности мосты.

Лемма 5. Пусть множество вершин связного граф G разбито на два непустых непересекающихся подмножества U и W. Тогда существует такое ребро е = uw, что и € U и w € W.

Доказательство. Возьмем две вершины х € U и у € W. В силу связности графа G существует простая (x, у) - цепь:

Пусть v_i - последняя вершина цепи, лежащая в U. Тогда v_i? у и

V_i+1 €W. Следовательно, ребро e_i+1 =u_i u_i+1 является искомым.

Теорема 1.2. Пусть G - обыкновенный (n, m, к) - граф. Тогда выполнено двойное неравенство

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

Легко понять, что каждая компонента связности графа G является полным графом. Поэтому



Можно считать, что n₁ ? п₂ ?… ? n_k.

Убедимся, что п₂ = 1. Предположим, что п₂ > 1. Пусть и - некоторая вершина графа К_n2. Удалим п₂ - 1 ребер, инцидентных вершине u, а затем добавим n₁ ребер, соединяющих вершину и с каждой вершиной графа К_n1, т.е. перенесем вершину и из второй компоненты связности в первую. Поскольку п₁> п₂ - 1, получим граф, имеющий п вершин, к компонент связности и больше чем m ребер. Это противоречит выбору графа G - Следовательно, п₂ = 1. Тогда п₂ =… = n_k = 1, т.е. все ребра графа G содержатся в полном графе К_n1 и n₁ = п - k + 1. Поэтому

Обратимся теперь к нижней оценке. Для ее проверки применим индукцию по числу ребер. Если m = 0, то п = к_: и требуемое неравенство очевидно. Пусть m > 0. Предположим, что для всех графов с числом ребер, меньшим чем m, оценка имеет место. Рассмотрим (п, m, k) - граф G. Пусть

G₁ - G - е, где е - некоторое ребро графа G. Тогда G₁ является (n, m - 1, k₁) - графом, где к₁ ? к + 1 в силу леммы 2. Следовательно,

m - 1 ? п - к₁ ? п - к - 1,

т.е. m ? п - к.

Следствие 1. Пусть G - обыкновенный (n, т) - граф. Если

то граф G связен.

Доказательство. Пусть к - число компонент связности графа G. Если

к ? 2, то



что невозможно. Следовательно, к = 1, т.е. граф G связен.

Следствие 2. Если G - произвольный (n, m₁, k) - граф G₁ является редукцией графа G. Тогда m ? m₁ ? n-k.

Доказательство. Пусть обыкновенный (n, m₁, k) - граф G₁ является редукцией графа G. Тогда m > m₁ > n - к.

3. Ориентированные графы

Пусть V, D - произвольные множества, причем V ??. Обозначим через V² декартов квадрат множества V.

Ориентированным графом или, короче, орграфом G называется тройка (V, D, ц)_: где ц - некоторое отображение множества D в множество V². Элементы множеств V и D называются соответственно вершинами и дугами орграфа G. Множества вершин и дуг орграфа G удобно обозначать через VG и DG соответственно. Если f - дуга, то ц(f) является упорядоченной парой (и, v), где и_: v Ј V. Дуга f выходит из вершины и и заходит в вершину v; в свою очередь и и v называются концевыми вершинами дуги f; в дальнейшем будем писать f = (а иногда даже - f = uv, если нет опасности возникновения путаницы).

При записи произвольного орграфа он, как правило, будет представляться в виде G = (V, D).

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

С каждым орграфом G = (V, D) естественно связать граф G_o = (V, Е), называемый основанием данного орграфа. Для получения основания необходимо в орграфе G заменить каждую дугу f = ребром е = uv

На рис. 8 изображены орграф и его основание



Рисунок 8

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

В которой

Такой маршрут принято называть (v_о, v_t) - ормаршрутом; вершины v_o и v_t называются соответственно начальной и конечной вершинами такого ормаршрута. Если v_o = v_t, то ормаршрут называют замкнутым. Количество дуг, составляющих ормаршрут, - это длина ормаршрута.

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

Нетрудно проверить, что существование (и, v;) - ормаршрута гарантирует существование простой (и, v) - орцепи.

Говорят, что вершина v достижима из вершины и, если существует (и, v) ормаршрут. Орграф G сильно связен или орсвязен, если любая его вершина достижима из любой другой вершины. Очевидно, сильно связный орграф является связным; обратное утверждение, разумеется, не верно.

Граф G называется ориентируемым, если он является основанием некоторого сильно связного орграфа.

Теорема 1.3. Связный граф G ориентируем тогда и только тогда, когда каждое его ребро не является мостом.

Доказательство. Пусть граф G является основанием орграфа Н и G содержит мост е. Тогда в Н имеется дуга f =, где и, v - концы ребра е. Очевидно, в Н нет (u, v) - ормаршрутов. Следовательно, граф G не является ориентируемым.

Обратно, пусть граф G не имеет мостов, т.е. каждое ребро графа G содержится в некотором цикле. Поскольку любой цикл является ориентируемым графом, в графе G существует максимальный ориентируемый подграф Н. Убедимся, что Н = G. Допустим, что это равенство не выполнено. В силу связности графа G существует ребро е, инцидентное вершине v из Н и не лежащее в Н. По предположению ребро е лежит в некотором цикле С. Обозначим через Q множество ребер цикла, не принадлежащих подграфу Н. Нетрудно понять, что, добавив к Н все ребра из множества Q, мы снова получим ориентируемый подграф в противоречие с выбором Н.

Пусть G - произвольный орграф. Полустепенью исхода degv вершины v называется число всех дуг, имеющих v в качестве начала. Аналогично, полустепень захода degv - это число всех дуг, для которых вершина v является концом. Орграф, содержащий п вершин и т дуг будем называть (n, т) - орграфом.

Полустепени исхода и полустепени захода связаны следующим очевидным образом.

Лемма 1. Пусть G - произвольный (n, т) - орграф. Тогда

Это утверждение аналогично лемме 1 из разд. 1.1; его часто называют орлеммой о рукопожатиях.

4. Матрицы, ассоциированные с графами

Пусть G - произвольный n-граф. Упорядочим множество вершин графа

VG = {v₁, v₂,…, v_n}.

Иными словами, занумеруем вершины графа числами от 1 до п. Граф, у которого множество вершин линейно упорядочено или, другими словами, занумеровано натуральными числами от 1 до n, где п - число вершин графа, называется помеченным графом.

Определим матрицу смежности А = A(G) = (Ь_ij)_nxn графа G, полагая a_ij равным числу ребер, соединяющих вершины v_i и v_j, причем при i = j каждую петлю учитываем дважды.

На рис. 9 приведен пример графа с некоторой нумерацией вершин и указана соответствующая матрица смежности.

Рисунок 9

Очевидно, матрица смежности - это квадратная симметрическая матрица. Сумма элементов i-й строки равна deg v_t, т.е.



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

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

Пусть а - произвольная подстановка на множестве {1, 2,…, п}. Определим матрицу S(у) = (у_ij)_nхn, полагая

Нетрудно проверить, что S(у^-1) = S^-1(у) и матрица

S^-1(у) AS(у) = S(у^-1) AS(у)

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

Таким образом, две матрицы смежности графа G подобны.

В силу этого корректно следующее определение. Характеристическим многочленом графа G называется характеристический многочлен любой из его матриц смежности. Совокупность всех корней характеристического многочлена, с учетом их кратности, называется спектром графа G.

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

Приведем теперь один пример утверждения, иллюстрирующего важность матриц смежности.

Теорема 1.4. Пусть А = (а_ij)_пхп - матрица смежности графа G без петель и A^l = (г_ij)_nxn, где l €N. Тогда г_ij равно числу (v_i, v_j) - маршрутов длины l.

Доказательство. Утверждение очевидно при l = 1. Пусть l > 1 и утверждение верно для l - 1. Тогда А^l-1 = (е_ij)_nxn, где е_ij равно числу (v_i, v_j) - маршрутов длины l - 1. Следовательно,

равно числу (v_i, v_j) - маршрутов длины l, так как каждый такой маршрут состоит из (v_i, v₈) - маршрута длины l - 1 и ребра, ведущего из предпоследней вершины v₈ маршрута в его последнюю вершину v_j.

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

Поскольку матрица смежности А графа G является вещественной симметрической матрицей, она ортогонально подобна некоторой вещественной диагональной матрице D:

А = T^-1DT.

Тогда, очевидно, A¹= T^-1D¹T. Данная формула позволяет быстро вычислять число (v_i, v_j) - маршрутов длины l для больших значений l, так как при этом нужно лишь найти D¹, обычным образом вычислить две матрицы Т, Т^-1 и два раза перемножить матрицы. Отметим, что главная диагональ матрицы D совпадает со спектром графа G.

Пусть теперь G - произвольный обыкновенный граф. Упорядочим множество его вершин



VG = {v₁, v₂,…, v_n}.

Определим матрицу Кирхгофа В = B(G)=(в_ij)_nxn, полагая

где A(G) - матрица смежности графа G. Иными словами,

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

Лемма 1. Алгебраические дополнения всех элементов матрицы Кирхгофа равны между собой.

Доказательство. Обозначим столбец (1, 1,…, 1)^t длины п, состоящий из единиц, через 1. Здесь, как обычно, через t мы обозначаем операцию транспонирования матриц.

Для матрицы Кирхгофа В = (в_ij)_пхп выполняется



Отсюда следует, что det B = 0 и rank В ? п - 1.

Если rank В < п - 1, то все алгебраические дополнения элементов матрицы В равны 0. Пусть rank В = п - 1 и Я - присоединенная к В матрица, составленная из алгебраических дополнений В_ij элементов в_ij т.е.

В силу свойств матрицы В получаем

Так как ВЯ = 0, любой столбец X матрицы Я удовлетворяет системе

ВХ = 0. Эта система линейных уравнений имеет ранг п - 1 и дефект 1. Так как В * 1 = 0, этой системе удовлетворяет столбец 1. Следовательно, столбцы матрицы В пропорциональны столбцу 1, откуда следует

B_i1=B_i2=…=B_in (i=1,2,…, n)

Аналогично получаем

B_1j=B_2j=…=B_nj (j=1,2,…, n)

Следовательно, все элементы матрицы Я одинаковы. ?

Пусть G - произвольный (n, m) - граф. Упорядочим множество вершин и множество ребер графа



VG = {v₁, v₂, …, v_n} и EG = {е₁ е₂,…, е_m}.

Будем говорить, что наш граф является дважды помеченным.

Определим теперь бинарную матрицу инцидентности

I = I(G) = = (l_ij)_nxm графа G, полагая

1) l_ij = 1 <=> вершина v_i инцидентна ребру e_j и e_j не является петлей;

2) l_ij = 0 во всех остальных случаях.

На рис. 10 приведен пример графа и его матрицы инцидентности. Здесь вершинам отвечают строки, а ребрам - столбцы

Рисунок 10

Заметим, что одна матрица инцидентности графа G получается из другой его матрицы инцидентности с помощью некоторой перестановки строк и некоторой перестановки столбцов.

Рассмотрим теперь произвольный (n, m) - орграф G = (V, D). Упорядочим множество вершин и множество дуг орграфа

V = {v₁, v₂, …, v_n} И D = {ѓ₁ ѓ₂,…, f_m}.

Определим матрицу инцидентности I = 1 (G) = (ьц)_пхт ографа G, полагая

1) l_ij = 1, если v_i - начало дуги fj и fj - не петля;

2) l_ij = - 1, если v_i - конец дуги fj и fj - не петля;

3) l_ij = 0 во всех остальных случаях

На рис. 11 приведен пример орграфа и его матрицы инцидентности. Здесь вершинам отвечают строки, а дугам - столбцы

Рисунок 11

Пусть G - произвольный граф. Превратим каждое его ребро в дугу, придав ребру одно из двух возможных направлений. Полученный орграф на том же самом множестве вершин будем называть ориентацией графа G. На рис. 11 приведен орграф, являющийся одной из ориентации графа, изображенного на рис. 10.

Зафиксируем некоторый обыкновенный граф G и возьмем некоторую его ориентацию Н. Кроме того, зафиксируем в G и Н одинаковую нумерацию вершин и одинаковую нумерацию соответствующих ребер и дуг.

Лемма 2. Пусть В = B(G) - матрица Кирхгофа обыкновенного графа G и I = 1 (H) - соответствующая матрица инцидентности некоторой его ориентации Н. Тогда В = I * I^t.

Доказательство. Если умножить i-ю строку матрицы I на i-й столбец матрицы I^t, то получим сумму квадратов элементов i-й строки матрицы I, которая равна, очевидно, deg v_i. Пусть теперь i-я строка матрицы I умножается на j-й столбец матрицы I^t. Если имеется дуга или дуга , то получим -1. Если такой дуги нет, то получим 0.

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



Эта формула связывает матрицу смежности А обыкновенного графа с матрицей инцидентности I его ориентации.

5. Леса, деревья, остовы

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

Теорема 2.1. Для (п, т) - графа G следующие условия эквивалентны:

G - дерево;

G - связный граф и m= n - 1;

G - ациклический граф и m = n - 1;

G - граф, в котором любые две вершины соединены единственной простой цепью;

G - ациклический граф, и добавление нового ребра приводит к появлению точно одного простого цикла.

Доказательство. 1) > 2). Индукцией по га проверим, что в дереве выполнено равенство m = n - 1. Если m = О, то, очевидно, n = 1. Пусть m > 0 и для всех деревьев с меньшим чем m числом ребер требуемое равенство выполнено. Рассмотрим дерево Gcm ребрами и выберем в нем произвольное ребро е. Очевидно, е - ациклическое ребро, поэтому граф G - е состоит из двух компонент связности G₁ и G₂, являющихся деревьями. Применяя к деревьям G1, G₂ предположение индукции, получаем, что в каждом из них число ребер на единицу меньше числа вершин. Отсюда сразу следует равенство m = n - 1.

2) > 3). Пусть граф G содержит циклическое ребро е. Ясно, что

G - е является связным (n, m - 1) - графом. В силу следствия 2 из тео-

ремы 1.2 имеем m - 1 ? n - 1, что невозможно.

3) > 4). Проверим сначала, что G - связный граф. Поскольку G ацикличен, его компоненты связности являются деревьями. Так как из 1) следует 2), в каждой компоненте связности число ребер на единицу меньше числа вершин. Отсюда вытекает, что m = n - к, где к - число компонент связности. Учитывая, что m = n - 1, получаем к = 1.

Предположим, что в G для двух вершин и, v существуют различные простые (u, v) - цепи P₁ и Р₂. Пусть Q - простая (u, x) - цеиъ, являющаяся длиннейшим общим началом цепей P₁ и Р₂. Обозначим через у, z вершины, следующие за вершиной х в P₁ и Р₂ соответственно. Очевидно, что ребро

f = xz не принадлежит цепи P₁. Отсюда следует, что подграф P₁ U Р₂ - f является связным графом. Поэтому f - не мост, следовательно, f принадлежит некоторому циклу, что невозможно.

4) > 5). Из условия следует, что в графе G нет циклов, в том числе и петель (если есть петля е = uu, то имеется две простые (и, u) - цепи: ими являются цепь из одной вершины и цепь ). Добавим к графу новое ребро g = vw, где v, w € VG. Тогда возникнет цикл, состоящий из простой (v, w) - цепи и ребра g. Единственность такого цикла следует из единственности простой (v, w) - цепи.

5) > 1). Из условия вытекает, что любые две вершины графа G соединены простой цепью, т.е. G - связный граф. Используя ацикличность графа G, заключаем, что G - дерево.

Следствие 1. Неодноэлементное дерево имеет по крайней мере две висячие вершины

Доказательство. Сумма степеней всех вершин дерева равна 2m = = 2п - 2. Отсюда следует, что дерево содержит не менее двух вершин степени 1.

Лемма 1. Пусть G - произвольный (n, m, к) - граф. G является лесом тогда и только тогда, когда m = п - к.

Доказательство. Если G - лес, то в каждой его компоненте связности число ребер на единицу меньше числа вершин. Отсюда немедленно вытекает равенство m = п - к.

Если G - не лес, то, отбрасывая не менее одного ребра, получим подграф графа G, являющийся (n, m₁, k) - лесом. Тогда т > т₁ - п - к в силу доказанного.

Пусть G - связный (n, m) - граф. Если G содержит хотя бы один цикл, то, удаляя из графа G некоторое ребро этого цикла, мы уменьшим число циклов по крайней мере на единицу, сохранив связность графа. Ясно, что последовательно разрушая циклы данного графа, можно прийти к остовному подграфу, являющемуся деревом. Такой подграф называется остовным деревом связного графа G. Поскольку дерево с п вершинами содержит п - 1 ребер, для получения остовного дерева из графа G нужно удалить m - п + 1 ребер. Если G - произвольный (n, m, k) - граф, то объединение остовных деревьев его компонент связности приводит к остовному лесу или остову графа G. Поскольку лес с п вершинами и к компонентами связности содержит n - к ребер, для получения остова из графа G нужно удалить

m - n + к ребер.

На рис. 12 показан граф G и один из его остовов Т

Рисунок 12

Число r*(G) - m - n + к называется цикломатическим числом, а число r(G) - n - k - рангом (n, m, k) - графа G. Следующее утверждение показывает, что если r*(G) равно 0 или 1, то r*(G) совпадает с числом циклов графа G.

Лемма 2. Пусть G - произвольный граф. Тогда

1) G ацикличен, если и только если r*(G) - 0;

2) G содержит единственный цикл, если и только если r*(G) - 1.

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

Проверим утверждение 2). Если ребро е содержится в единственном цикле графа G, то подграф G - е является остовом. Отсюда (m - 1) - - n + k = 0, т.е. r*(G) = 1.

Обратно, пусть Т - произвольный остов графа G. Равенство r*(G) = 1 означает, что разность между числами ребер графа G и его остова Т равна 1. Отсюда следует, G - Т + е для некоторого ребра е. Ребро е добавляется к некоторой компоненте связности остова Т, поэтому граф G - Т + е содержит единственный цикл.

Лемма 3. Любой ациклический подграф графа G содержится в некотором его остове.

Доказательство. Достаточно рассмотреть случай, когда G - связный n-граф. Пусть Н - ациклический подграф графа G. Обозначим через Н₁ максимальный ациклический подграф, содержащий Н. Ясно, что H₁ включает все вершины графа G. Проверим, что H₁ связен. Предположим, что граф H₁ несвязен. Обозначим через U множество вершин одной из компонент связности графа H₁, а через W - множество всех остальных вершин этого графа. В силу леммы 5 из разд. 1.2 существует ребро е, соединяющее вершины множеств U и W. Ребро е не образует цикла с ребрами подграфа H₁, поэтому подграф H₁ + е ацикличен, что противоречит выбору H₁.