Деревья.

1. Связный граф G(V, E), не имеющий циклов, называется деревом. Следующая теорема перечисляет некоторые основные свойства деревьев.

Теорема 1. Пусть граф G(V, E) имеет n вершин. Тогда следующие утверждения эквиваленты.

1) G является деревом;

2) G не содержит циклов и имеет n - 1 ребер;

3) G связен и имеет n - 1 ребер;

4) G связен, но удаление любого ребра нарушает связность;

5) любые две вершины графа G соединены ровно одним путем;

6) G не имеет циклов, но добавление любого ребра порождает ровно один цикл. При n = 1 утверждение очевидно, поэтому считаем n> 2. 1) 2). По определению G не имеет циклов. Рассмотрим некоторое ребро = (v₁, v₂) и удалим его. Получим граф G'. В графе G' нет пути из v₁ в v₂, т.к. если бы такой путь был, то в графе G был бы цикл. Значит G' не связен и не имеет циклов. Значит он состоит из двух компонент, являющихся деревьями с числом вершин n₁ и n₂ соответственно (n₁+n₂ = n). По индуктивному предположению G' имеет n₁-1+n₂-1 ребер. Следовательно, граф G имеет n-1 ребер.

2) 3). Если бы G был несвязен, то каждая его компонента представляла бы собой связный граф без циклов. Из предыдущего имеем, что число ребер в каждой компоненте меньше на один числа ее вершин. Значит, общее число ребер меньше числа вершин по крайней мере на два, что противоречит тому, что G имеет n-1 ребер.

3) 4). Удаление любого ребра приводит к графу с n вершинами и n-2 ребрами, который не может быть связным в силу Факта 2 § 1.

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

5) 6). Если бы G содержал цикл, то любые две вершины на цикле соединялись бы по крайней мере двумя путями. Добавим теперь к графу G ребро =(v₁, v₂). Тогда образуется цикл, т.к. вершины v₁ и v₂ уже соединены путем. Ясно, что цикл единственный.

6) 1). Если бы G был несвязен, то добавление ребер, соединяющих вершины из разных компонент, не приводит к образованию цикла.

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

Действительно, пусть v₁,..., v_n - множество вершин, тогда имеем

В силу связности d(v₁) 1, отсюда и следует утверждение.

2. Для графа G(V, E) определим два полезные понятия.

Вершинный подграф G(V, E') - это граф на множестве вершин и ребрами E' E, такими, что оба конца ребра е E' принадлежат V'.

Реберный подграф G(V', E') - это граф, определяемый подмножеством ребер Е с: Е и множеством вершин V' с V, состоящим из концевых вершин ребер из Е. Остовным (покрывающим) деревом графа G(V, Е) называется его реберный подграф с множеством вершин V, являющийся деревом.

Факт 2. Граф G(V, Е) имеет остовное дерево тогда и только тогда, когда он связен. • Предложим процедуру построения остовного дерева. Ясно, что если граф G не связен, то он не может иметь остовного дерева.

Пусть граф связен. Если в графе нет ребра, удаление которого сохраняет связность графа, то G - дерево.

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

Рассмотрим теперь известную проблему нахождения минимального остовного дерева. Пусть G(V, Е) неориентированный граф и пусть каждому ребру е Е поставлено в соответствие положительное число (е), называемое его весом. Требуется найти связный реберный подграф G'(V', Е'), такой, что V' = V, причем сумма

минимальна.

Ясно, что граф G(V', Е') должен быть деревом. Действительно, если

G(V', Е') содержит цикл, то тогда любое ребро цикла можно удалить из графа и тем самым уменьшить суммарный вес ребер графа G(V', Е').

Факт 3. Пусть V - произвольная вершина связного графа G(V, Е) и пусть е-смежное с ней ребро, для которого (e) минимально для всех ребер, смежных с V. Тогда существует минимальное остовное дерево для G(V, Е), которое содержит ребро е.

• Пусть Т - любое минимальное остовное дерево для G(V, Е). Если е не является ребром Т, добавим е к Т. Поскольку Т - дерево, то в силу теоремы, при этом образуется цикл. Возьмем ребро е', лежащее на цикле и смежное с вершиной V, и удалим его. Поскольку , то получившееся дерево также минимально.

Следующая теорема дает алгоритм построения минимального остовного дерева, известный под названием алгоритма Краскала.

Теорема 4. Пусть G(V, Е) связный граф с n вершинами. Тогда следующая процедура приводит к построению минимального остовного дерева.

1) Выберем ребро e₁, обладающее в G наименьшим весом.

2) Определим по индукции последовательность ребер е₂,..., e_n-1 (*), выбирая на каждом шаге ребро, отличное от предыдущих, с наименьшим весом и не образующее цикла с уже выбранными ребрами. Полученный подграф Т графа G, образованный ребрами e₁,..., e_n-1, и есть искомое остовное дерево.

Поскольку Т не содержит циклов и имеет n-1 ребер, то Т - остовное дерево, в силу теоремы 1. Покажем, что сумма весов всех ребер Т минимальна. Предположим, что в G существует некоторое другое остовное дерево Т', такое, что М(Т') < М(Т). Пусть e_k -первое ребро из последовательности (*) теоремы, которое не принадлежит Т'. Добавим ребро e_k к Т' - тогда в Т' образуется цикл С, содержащий ребро e_k.Цикл С содержит ребро е, принадлежащее Т' и не принадлежащее Т. Удалим из Т' ребро е и добавим ребро е_k. Полученный подграф Т также является остовным деревом. По построению , поэтому М(Т) М(Т'). При этом число общих ребер у Т и Т на одно больше, чем у Т’ и Т. Повторяя описанную процедуру, можно преобразовать Т' в Т, причем сумма весов на каждом шаге не увеличивается. Значит, М(Т) М(Т), что противоречит допущению.

Сделаем теперь несколько замечаний о применениях понятия остовного дерева.

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

3. В этом пункте мы получим формулу Кирхгофа для числа остовных деревьев произвольного неориентированного графа и формулу Кэли для числа остовных деревьев полного графа. Получим сначала подготовительные результаты. Пусть G(V, E) ориентированный граф без петель, где V = {v₁,..., v_n}, E={e₁,..., e_m}. Определим матрицу инцидентности А графа G следующим образом:

A=(a_ij), i= 1,..., n, j= 1,..., m, где

+ 1, если v_i начальная вершина е_j;

a_ij = - 1, если v_i конечная вершина е_j;

0, если v_i не инцидентна e_j.

Напомним, что минором называется определитель подматрицы, полученный из А строками i₁,..., i_p и столбцами j₁,..., j_p.

Факт 5. Миноры матрицы инциденций А равны + 1, - 1 или 0. По определению, каждый столбец матрицы А имеет один элемент +1 и один -1, остальные элементы 0. Рассмотрим произвольную подматрицу

Если имеется столбец из нулей, то ее определитель равен нулю. Если имеется столбец, содержащий один ненулевой элемент (+ 1 или - 1), то утверждение следует по индукции, т.к. оно верно для размера р = 1.

Если все столбцы содержат оба элемента +1 и -1, то суммированием всех строк получаем нулевую строку и, значит, определитель равен нулю.

Факт 6. Минор А матрицы инциденций А ориентированного графа G(V, Е) отличен от нуля (т.е. равен + 1 или - 1) тогда и только тогда, когда соответствующий скелетный граф реберного подграфа, определенного Е' = {е_j1 ,..., } является деревом.

Пусть не является деревом. Тогда, поскольку число ребер равно n-1, то по теореме 1 должен содержать цикл. Если взять сумму столбцов, которые соответствуют ребрам простого цикла в , то получим нулевой столбец. Минор в этом случае равен нулю. Обратно, пусть дерево. Если n=2, то состоит из одного ребра. Соответствующая матрица А имеет размер 2 1, а ее миноры равны +1 и -1. Предположим, что если дерево с k-1 вершинами, то соответствующий минор ненулевой, и пусть G имеет k вершин. Пусть Е' ={ }- соответствующий ему набор ребер, a { }- набор вершин. Поскольку каждое дерево имеет по крайней мере 2 конечные вершины, то среди k - 1 вершин , имеется одна конечная, скажем v_t. Разложим минор по строке t. Ясно, что эта строка содержит единственный, отличный от нуля элемент (+ 1 или - 1) и k - 2 нулей. Значит, с точностью до знака, минор равен минору, который соответствует дереву ’, полученному из удалением вершины v_t и всех ребер, смежных с ней. По индуктивному предположению данный минор отличен от нуля.

Нам понадобится известная формула Бинэ-Коши из линейной алгебры. Пусть - матрица и - матрица, где . Тогда справедливо следующее тождество

Теперь мы в состоянии доказать теорему Кирхгофа.

Теорема 7. Пусть М-((n-1) m)-матрица, полученная из матрицы инциденций А ориентированного графа G(V, E) вычеркиванием некоторой строки. Тогда det(M*M') равен числу остовных деревьев соответствующего скелетного графа. (Здесь М' - транспонированная матрица М).

По формуле Бинэ-Коши имеем

поскольку

Далее, на основе факта 6 скелетный граф реберного подграфа, определенного ребрами Е'={ } является остовным деревом тогда и только тогда, когда . Суммирование распространено по всем Е' и каждое Е' появляется точно один раз. Каждое Е', соответствующее дереву, дает 1, не соответствующее дереву, дает 0.

Если дан произвольный неориентированный граф G(V, Е), то нет необходимости приписывать ребрам ориентацию, определять матрицы М и М' и перемножать их. Можно вычислить М и М' непосредственно, исходя из графа G(V, Е). Пусть V = {v₁, v₂,..., v_n}. Пусть вычеркиваемая строка в матрице инциденций А соответствует v_n. Нетрудно заметить, что элемент (М*М')_ii- это степень вершины v_i, а элемент (М*М')_ij при - это число ребер, соединяющих v_i с v_j, взятое со знаком минус.

Пример. Рассмотрим граф G:

Тогда

и значит det(M*M') = 4.

Значительный интерес имеет случай полного неориентированного графа на n вершинах. Число покрывающих деревьев такого графа найдено Кэли.

Теорема 8. Число остовных деревьев полного неориентированного графа на n вершинах равно n^n-2.

Матрица М*М` в этом случае имеет вид:

Отнимем первый столбец от остальных и получим

Теперь прибавим все строки к первой строке, получаем

Ясно, что определитель последней матрицы есть n^n-2.

4. Вернемся еще раз к вопросу о порождении подстановок транспозициями. Пусть S_n - группа всех подстановок степени n, Т_n - множество всех транспозиций. Напомним, что некоторое множество элементов М из группы G является системой образующих для G или порождает G, если множество произведений с конечным числом сомножителей элементов из М, взятых с положительными и отрицательными степенями, совпадают с группой G.

Поставим теперь вопрос, когда произвольное множество транспозиций R_n из Т_n является системой образующих для S_n? Пусть R_n={t₁,..., t_r}. Поставим множеству R_n в соответствие граф Г(R_n), называемый графом Пойа и определяемый следующим образом:

Вершинами графа Г(R_n) являются элементы 1, 2,..., n. Каждой , если t_i=(р, q) в Г(R_n) соответствуетребро, инцидентное вершинам р и q. Может быть доказана

Теорема 9. Множество транспозиций R_n={t₁,..., t_r}, (r n-1)тогда и только тогда порождает симметрическую группу S_n, когда соответствующий граф Пойа Г(R_n) связен.

Следствие 1. Множество из n-1 транспозиций R_n порождает S_n тогда и только тогда, когда соответствующий граф Пойа Г(R_n) является деревом.

Следствие 2. Число систем образующих симметрической группы S_n, состоящих из n-1 транспозиций, равно n^n-2.

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

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

Такое изображение будем называть плоским графом, а граф, изоморфный плоскому, назовем планарным. Легко указываются примеры планарных графов. Например, К_2.3, К₄. В то же время не удается установить планарность графов К_{3, 3}, К₅. Ниже будет доказано, что графы К_{3, 3}, К₅ не являются планарными. Отметим, что справедлив факт, приводимый без доказательства.

Теорема 1. Почти все графы не являются планарными.

Рассмотрим сначала укладку графов в действительном трехмерном пространстве R₃.

Теорема 2. Каждый граф укладывается в R₃.

Все вершины произвольного графа G помещаем в различных точках координатной оси х. Рассмотрим пучок плоскостей, проходящих через ось х, и зафиксируем |Е| различных таких плоскостей. Теперь каждое ребро (u, v) изобразим полуокружностью, проходящей в соответствующей плоскости через вершины u, v. Ясно, что различные ребра не будут пересекаться кроме как в общих вершинах.

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

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

Пример. Приведенный ниже граф имеет 4 грани.

Пусть G = (V, Е) - плоский граф, такой, что n = |V|, m = |E|, f- число граней.

Теорема 3 (Эйлер). Для всякого плоского связного графа G справедливо соотношение

n-m+f=2

Доказываем индукцией по m при фиксированном п. Поскольку G связен, то m n-1. Пусть m=n-1. В силу связности G он является деревом. Значит в G нет циклов и потому f=1 и теорема справедлива для этого случая.

Пусть она справедлива для всех m, таких, что n - 1 < m < mi. Докажем ее для mi.

Пусть G - связный граф, плоский с n вершинами и mi ребрами, имеющий f граней.

Поскольку m₁> n-1, то G содержит цикл С. Пусть е - ребро, принадлежащее циклу. Тогда е принадлежит разным граням. Удалим ребро е из графа G. Тогда эти две грани сливаются в одну, при этом граф полученный из G удалением е, связен, поскольку е лежит на цикле.

Граф G¹ имеет n вершин, m₁-1 ребер, f-1 граней. По предположению индукции справедливо соотношение

n-(m₁-l)+(f-l)=2

Отсюда n-m₁+f= 2, что и доказывает утверждение.

Следовательно, число граней планарного графа определяется соотношением

f=m-n+2

3. Используя теорему Эйлера можно доказывать непланарность конкретных графов.

Пусть G - планарный граф. Обозначим через - число граней, ограниченных k ребрами.

Поскольку рассматриваются графы без петель и параллельных ребер, то

Справедливы следующие соотношения:

В первом соотношении просуммированы все грани, во втором - ребра, ограничивающие каждую грань, при этом каждое ребро учитывается дважды.

Рассмотрим граф К_{3, 3}. Для него n=6, m=9. Пусть К_{3, 3} - плоский граф. Тогда должно быть f= 9 - 6+2 = 5 граней.

Для графа К_{3, 3} нет циклов длины 3, поэтому =0. Следовательно, должно быть выполнено

Отсюда получаем (т.к. , что -2 0 - противоречие. Рассмотрим теперь граф К₅. Для него n=5, m = 10. Если бы граф К₅ был плоским, то должно быть f= 10 - 5+2 = 7. Следовательно, должно быть выполнено

Отсюда следует, что -1 0- противоречие.

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

4. Имеется несколько критериев планарности графа. Приведем без доказательства критерий Понтрягина-Куратовского. Для этого определим понятие гомеоморфизма графа. Операцией разбиения ребра е=(u, v) называют операцию замены ребра е двумя ребрами e₁=(u, w) и e₂=(w, v), где w - новая вершина. Два графа называют гомеоморфными, если они могут быть получены из одного графа с помощью операций разбиения ребер.

Справедлива

Теорема (Понтрягин-Куратовский). Граф планарен тогда и только тогда, когда он не содержит подграфов, гомеоморфных К_{3, 3} или К₅.

5. Для характеристики непланарных графов используются различные меры, из которых укажем две. Толщина графа G есть число t(G) - наименьшее число его планарных подграфов, объединение которых дает граф G. Очевидно, что толщина планарного графа есть 1.

Приведем значение толщины некоторых графов:

Здесь [x], ]x[ - ближайшие целые для х, удовлетворяющие [x] x ]x[.

Род графа G определяется как минимальное число ручек (G), которые надо прикрепить к сфере, чтобы уложить граф G. Ясно, что для плоского графа G (G)=0 поскольку укладка на плоскости равносильна укладке на сфере. Приведем значения рода некоторых графов.