Учебно-методический комплекс по дисциплине «Теория конечных графов и ее приложения» Алексеев В. Е, Захарова Д. В

3. Важнейшие классы графов

Деревья

Деревом называется связный граф, не имеющий циклов. Граф без циклов называют лесом.

Во всяком дереве, в котором больше одной вершины, имеется не менее двух вершин степени 1. Такие вершины называют листьями.

Теорема о свойствах деревьев Если G – дерево, то

1) число ребер в нем на 1 меньше числа вершин;

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

3) при добавлении к G любого нового ребра образуется цикл;

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

for to do

найти в дереве Т наименьший лист а;

пусть b – вершина, смежная с a;

положить ;

удалить из T вершину a
По коду Прюфера легко определить степени вершин дерева: степень вершины на 1 больше числа вхождений этой вершины в . Зная степени, можно восстановить дерево по коду с помощью следующей процедуры.
Восстановление дерева по коду Прюфера
Создать граф с , ;

for to do

найти наименьшее а с ;

добавить к множеству E ребро ;

уменьшить и на 1;.

добавить к множеству E ребро , где x и y – позиции ненулевых элементов в таблице степеней.
Код Прюфера устанавливает взаимно однозначное соответствие между множеством всех деревьев с множеством вершин и множеством упорядоченных наборов длины , составленных из элементов множества . Отсюда следует формула для числа таких деревьев.
Теорема о числе деревьев (формула Кэли). Число помеченных деревьев с вершинами равно .
Корневым деревом называют дерево с выделенной вершиной – корнем.

Высота корневого дерева – это расстояние от корня до самого удаленного листа.

Если в корневом дереве T путь, соединяющий вершину с корнем, проходит через вершину , то говорят, что – предок , а – потомок . В частности, каждая вершина является предком и потомком самой себя. Множество всех предков вершины порождает путь из корня в . Множество всех потомков вершины порождает дерево с корнем , оно называется ветвью дерева T в вершине . Если предок и потомок соединены ребром, то они называются соответственно отцом и сыном. Компактный и полезный во многих случаях способ задать корневое дерево состоит в указании для каждой вершины ее отца (отцом корня иногда считают саму эту вершину).

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

Каждой вершине дерева приписывается код вершины – слово в алфавите {0,1}. Он строится по следующим правилам. Если – лист (но не корень), то , где – пустое слово. Код вершины , не являющейся листом, определяется после того, как построены коды всех ее сыновей. Пусть – эти коды, упорядоченные лексикографически: . Тогда полагаем . Код корня и является каноническим кодом дерева. На рисунке 4 показаны дерево с корнем в вершине 12 и таблица кодов его вершин.

1
2
3	01
4
5	01
6
7
8	010011
9
10	0011
11	01
12	0101000111001100100111

Рис. 4.
Канонический код любого дерева обладает свойствами:

1) число нулей в нем равно числу единиц;

2) в каждом его начальном отрезке число единиц не превосходит числа нулей.

Используя эти свойства, можно легко восстановить дерево по его коду. Код дерева имеет вид: , где – ветви в сыновьях корня. Если – первый начальный отрезок слова , в котором число нулей равно числу единиц, то . Таким образом, код первой ветви получается из слова отбрасыванием первой и последней букв. Аналогично находятся коды остальных ветвей. Если код какой-то ветви оказывается пустым словом, то эта ветвь состоит из единственной вершины. К остальным ветвям процедура применяется рекурсивно.

Так как дерево по коду восстанавливается однозначно, то из равенства следует, что корневые деревья и изоморфны. Обратно, пусть и – изоморфные корневые деревья. Докажем индукцией по числу вершин, что их коды совпадают. Пусть и – ветви в сыновьях корней деревьев и соответственно. Тогда существует такая перестановка номеров , что для каждого . По предположению индукции . Значит, наборы и различаются только порядком слов. После того, как каждый из них будет лексикографически упорядочен, эти наборы станут одинаковыми. Поэтому коды и совпадут. Таким образом, справедлива
Теорема об изоморфизме корневых деревьев. Корневые деревья и изоморфны тогда и только тогда, когда .
Описанное кодирование можно применить и для распознавания изоморфизма обычных (не корневых) деревьев. Допустим, нужно сравнить деревья и . Сначала находим центры обоих деревьев. Ясно, что при изоморфизме центр должен перейти в центр. Если центр каждого из деревьев состоит из одной вершины, выберем эти вершины в качестве корней, затем построим канонические коды корневых деревьев и сравним их. Если центр одного дерева – одна вершина, а другого – две, то эти деревья не изоморфны. Допустим, каждый из центров состоит из двух вершин. Если удалить ребро, соединяющее две центральные вершины, то дерево разобьется на два корневых дерева (с корнями в бывших центральных вершинах). Построив коды этих корневых деревьев, получаем для дерева пару слов ), а для дерева – пару слов . Остается сравнить эти (неупорядоченные) пары.
Пусть G – связный граф. Его каркас (остов, остовное дерево) – это остовный подграф, являющийся деревом. В общем случае (граф может быть несвязным) каркас определяется как лес, в котором каждая компонента связности является каркасом компоненты связности графа. У любого графа есть хотя бы один каркас. Его можно найти, удаляя цикловые ребра (ребра, принадлежащие циклам) до тех пор, пока все циклы не будут разрушены.

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

Заметим, что матрица – вырожденная, так как сумма элементов каждой строки равна 0.

Теорема Кирхгофа [4]. Если G – связный граф с не менее чем двумя вершинами, то алгебраические дополнения всех элементов матрицы равны между собой и равны числу каркасов графа G.

Двудольные графы

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

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

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

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

Теорема о числе граней (формула Эйлера). Количество граней в любой плоской укладке планарного графа, имеющего n вершин, m ребер и k компонент связности, равно .
Следствие 1. Если в планарном графе n вершин, , и m ребер, то .
Следствие 2. Если в планарном графе n вершин, , m ребер и нет циклов длины 3, то .
Следствие 3. В любом планарном графе имеется вершина степени не более 5.
Операция подразбиения ребра действует следующим образом. Из графа удаляется это ребро, к нему добавляется новая вершина c и два новых ребра и . Граф называется подразбиением графа , если первый можно получить из второго последовательностью подразбиений ребер.
Теорема Понтрягина–Куратовского) [4,5]. Граф планарен тогда и только тогда, когда у него нет подграфа, являющегося подразбиением графа или графа.
Операция стягивания ребра определяется следующим образом. Вершины a и b удаляются из графа, к нему добавляется новая вершина c и она соединяется ребром с каждой вершиной, с которой была смежна хотя бы одна из вершин . Граф G называется стягиваемым к графу H, если H можно получить из G последовательностью операций стягивания ребер.
Теорема Вагнера [5]. Граф планарен тогда и только тогда, когда у него нет подграфа, стягиваемого к графу или графу .
Рассмотрим один из алгоритмов проверки планарности. Предполагается, что граф связен и в нем нет шарниров. Алгоритм строит плоскую укладку графа или определяет, что граф не планарный.

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

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

В примере на рисунке 5 выделены вершины и ребра подграфа , – грани этого подграфа. Справа показаны три сегмента относительно этого подграфа.

Рис. 5.
Грань называется допустимой для некоторого сегмента, если все контактные вершины этого сегмента принадлежат этой грани. Если обозначить через множество допустимых граней для сегмента , то в примере имеем , , .

Распознавание планарности и построение плоской укладки [4]
Найти в графе какой-нибудь простой цикл и уложить его.

Пока есть не уложенные ребра, повторять

найти грани уложенного подграфа, сегменты и допустимые грани для каждого сегмента;

если для некоторого сегмента нет допустимых граней, то граф не планарен, стоп;

если есть сегменты, имеющие только одну допустимую грань, то пусть – такой сегмент, иначе выбрать любой сегмент ;

в сегменте найти путь , соединяющий две контактные вершины этого сегмента и не содержащий других контактных вершин;

уложить путь в одну из допустимых граней для сегмента .
В применении к рассмотренному примеру в качестве должен быть выбран сегмент , а в качестве пути можно взять, например, путь (3, 1, 7, 8). Он должен быть уложен в грань , после чего она разобьется на две новых грани.

Задачи

3.1. Сколько ребер в лесе с n вершинами и k компонентами связности?

3.2. Сколько ребер в графе с n вершинами, если в нем имеется единственный цикл?
3.3. Перечислите все абстрактные деревья с 6 (7) вершинами.
3.4. В дереве имеется 40 вершин степени 4, все остальные вершины – листья. Сколько

листьев в этом дереве?

3.5. В дереве имеется ровно три листа , причем , ,

. Сколько всего вершин в этом дереве?
3.6. Дерево имеет две центральные вершины, а его радиус равен 6. Чему равен диаметр

этого дерева?

3.7. Постройте код Прюфера для дерева, изображенного на рисунке.

3.8. Восстановите дерево по коду Прюфера (4, 1, 6, 2, 2, 2, 7, 6).
3.9. Сколько имеется помеченных корневых деревьев с n вершинами?
3.10. Сколько различных (помеченных) каркасов у графа ?
3.11. Сколько попарно неизоморфных каркасов у графа ?
3.12. С помощью теоремы Кирхгофа найдите число каркасов у графа .
3.13. Найдите два неизоморфных дерева с одинаковыми наборами степеней вершин.
3.14. Найдите дерево с наименьшим числом вершин, не имеющее нетривиальных

автоморфизмов.

3.15. Постройте канонический код дерева из задачи 3.8, взяв в качестве корня вершину 2.
3. 16. Восстановите дерево по каноническому коду .
3.17. Какие из следующих графов являются двудольными: 1) ; 2); 3) ;

4) ?

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

ребро к графу а) ; б) ; в) ?

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

двудольный граф?

3.20. Двудольный граф имеет k компонент связности. Каким числом способов его можно

разбить на две доли?

3.21. При каких значениях k граф является двудольным?

3.22. Какие из следующих графов планарны: 1) ; 2); 3); 4) ?

3.23. Какое наибольшее число граней может быть у плоского графа с 5 вершинами?

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

планарный граф?

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

получился непланарный граф?

3.26. При каких значениях k граф является планарным?
3.27. Примените алгоритм распознавания планарности а) к графу из задачи 1.16;

б) к графу ; в) к графу .

3.28. Плоский граф называется плоской триангуляцией, если граница каждой грани

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

плоской триангуляции. Сколько ребер у плоской триангуляции с вершинами?
3.29*. Граф называется расщепляемым, если множество его вершин можно разбить на два

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

Докажите, что граф расщепляемый тогда и только тогда, когда в нем нет

порожденного подграфа, изоморфного какому-нибудь из графов , , .

3.30*. Докажите, что почти все графы не двудольные.
3.31*. Докажите, что почти все графы не планарные.
3.32*. Покажите, что алгоритм построения кода Прюфера можно реализовать так, что

время его работы будет .

3.33*. Покажите, что алгоритм восстановления дерева по коду Прюфера можно

реализовать так, что время его работы будет .

<< предыдущая страница следующая страница >>