- •Теория графов
- •Деревья
- •Определения
- •Основные свойства деревьев
- •Ориентированные деревья
- •Деревья покрытия. Остовы
- •Раскраска графов
- •Алгоритм правильной раскраски
- •П ланарность
- •Плоские и планарные графы
- •Грани плоского графа. Формула Эйлера
- •Теорема Потрягина-Куратовского
- •Алгоритм укладки графа на плоскости
- •Алгоритм укладки графа на плоскости
-
Теория графов
-
Деревья
-
Определения
-
-
-
Деревом называется связный граф, не содержащий циклов.
-
Любой граф без циклов называется лесом (или ациклическим графом). Таким образом, компонентами леса являются деревья.
-
На рисунке изображены все деревья с 6 вершинами:
|
|
|
|
|
|
-
Граф, в котором выполняется равенство , называется древовидным.
-
Пусть - ациклический граф. Если в нем при соединении ребром любой пары несмежных вершин, получится граф ровно с одним простым циклом, то граф будем называть субциклическим.
-
Основные свойства деревьев
Следующая теорема устанавливает, что два из четырех свойств – связность, ацикличность, древовидность и субцикличность – характеризуют граф как дерево.
-
Для – графа следующие утверждения эквивалентны:
-
– дерево;
-
Любые две несовпадающие вершины графа соединяет единственная простая цепь;
-
– связный граф, и любое ребро есть мост;
-
– связный граф и древовидный;
-
– ациклический граф (лес) и древовидный;
-
– ациклический граф (лес) и субцикличекий;
-
– связный, субциклический и неполный, ;
-
– древовидный и субциклический, исключая и ;
-
(1->2): Если – дерево, то любые две его несовпадающие вершины соединяет единственная простая цепь.
От противного. Пусть существуют две цепи (см. рис.).
Тогда - простой цикл.
(2->3): Если любые две несовпадающие вершины графа соединяет единственная простая цепь, то – связный граф, и любое ребро есть мост.
Имеем: (число компонент связности). Далее от противного. Пусть ребро - не мост. Тогда в концы этого ребра связаны цепью. Само ребро в исходном графе – вторая цепь, что противоречит условию.
(3->4): Если – связный граф, и любое ребро есть мост, то – связный и древовидный ().
Индукция по (числу вершин). Если , то (число ребер). Пусть равенство выполняется для всех графов с числом вершин меньше . Докажем, что оно выполняется и для вершин.
Удалим из ребро , являющееся мостом. Получим две компоненты связности и , для которых верно равенство . Т.е. , . Тогда .
(4->5): Если – связный и древовидный (), то – ациклический граф (лес) и древовидный ().
От противного. Пусть есть цикл с вершинами и ребрами. Остальные вершин связаны с этим циклом ребрами, т.к. граф связный. Следовательно, , что противоречит условию .
Остальное без док-ва.
-
Ориентированные деревья
-
Ориентированным деревом (или ордеревом, или корневым деревом) называется орграф со следующими свойствами:
-
существует единственный узел, в который не входит ни один другой узел. Он называется корнем ордерева;
-
во все остальные узлы входит только по одному узлу;
-
каждый узел достижим из корня.
-
Ордерево обладает следующими свойствами:
1. ;
2. если в ордереве отменить ориентацию ребер, то получится обычное дерево;
3. для каждого узла существует единственный путь, ведущий в этот узел из корня;
4. подграф, определяемый множеством узлов, достижимых из узла , является ордеревом с корнем . Это ордерево называется поддеревом узла .
-
Концевая вершина ордерева называется листом. Путь из корня в лист называется ветвью. Длина наибольшей ветви ордерева называется высотой. Уровень узла ордерева – это расстояние отт корня до узла. Сам корень имеет уровень 0. Узлы одного уровня образуют ярус дерева.