Лекции по теме Деревья и графы

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

    1. Деревья

      1. Определения

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

  2. Любой граф без циклов называется лесом
    (или ациклическим графом). Таким образом,
    компонентами леса являются деревья.

  1. На
    рисунке изображены все деревья с 6
    вершинами:

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

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

      1. Основные
        свойства деревьев

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

  1. Для
    – графаследующие утверждения эквивалентны:

    1. – дерево;

    2. Любые две несовпадающие вершины графа
      соединяет единственная простая цепь;

    3. – связный граф, и любое ребро есть
      мост;

    4. – связный граф и древовидный;

    5. – ациклический граф (лес) и древовидный;

    6. – ациклический граф (лес) и субцикличекий;

    7. – связный, субциклический и неполный,;

    8. – древовидный и субциклический,
      исключаяи;

(1->2): Если
– дерево, то любые две его несовпадающие
вершины соединяет единственная простая
цепь.

От противного. Пусть существуют две
цепи
(см. рис.).

Тогда
— простой цикл.

(2->3): Если любые две несовпадающие
вершины графа
соединяет единственная простая цепь,
то
связный граф, и любое ребро есть мост.

Имеем:
(число компонент связности). Далее от
противного. Пусть ребро— не мост. Тогда вконцы этого ребра связаны цепью. Само
ребров исходном графе – вторая цепь, что
противоречит условию.

(3->4): Если

связный граф, и любое ребро есть мост,
то– связный и древовидный ().

Индукция по
(числу вершин). Если,
то(число ребер). Пусть равенствовыполняется для всех графовс числом вершин меньше.
Докажем, что оно выполняется и длявершин.

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

(4->5): Если
– связный и древовидный (),
то– ациклический граф (лес) и древовидный
().

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

Остальное без док-ва.

      1. Ориентированные
        деревья

  1. Ориентированным деревом (или ордеревом,
    или корневым деревом) называется орграф
    со следующими свойствами:

  • существует единственный узел, в который
    не входит ни один другой узел. Он
    называется корнем ордерева;

  • во все остальные узлы входит только по
    одному узлу;

  • каждый узел достижим из корня.

  1. Ордерево
    обладает следующими свойствами:

1.
;

2. если в ордереве отменить ориентацию
ребер, то получится обычное дерево;

3. для каждого узла существует единственный
путь, ведущий в этот узел из корня;

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

  1. Концевая вершина ордерева называется
    листом. Путь из корня в лист называется
    ветвью. Длина наибольшей ветви ордерева
    называется высотой. Уровень узла
    ордерева – это расстояние отт корня
    до узла. Сам корень имеет уровень 0. Узлы
    одного уровня образуют ярус дерева.

      1. Деревья покрытия.
        Остовы

  1. Пусть
    – связный граф. Деревом покрытия графаназывается подграф, который является
    деревом, и множество вершин которого
    совпадает с множеством вершин графа.

Заметим, что связный граф может иметь
много различных деревьев покрытия.
(Пример)

  1. Каждый
    связный граф содержит в себе дерево
    покрытия.

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

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

  1. Пусть
    – несвязный граф. Остовом (или каркасом)
    графаназывается объединение деревьев
    покрытия всех его компонент связности.

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

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

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

  1. Число
    называется цикломатическим числом
    графа.

    1. Раскраска графов

  1. Пусть
    — некоторый граф,натуральное
    число. Произвольная функция виданазываетсяраскраской графа.

  2. Раскраска называется правильной,
    еслилюбых смежных вершини

  3. Граф, для которого
    правильнаяраскраска, называетсяраскрашиваемым
    (или просто раскрашиваемымцветами).

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

  1. Минимальное число
    ,
    при котором графявляетсяраскрашиваемым,
    называетсяхроматическим числом этого графа и обозначается.
    Если,
    то графназываетсяхроматическим.
    Правильнаяраскраскаприназываетсяминимальной раскраской.

  1. Одна
    из правильных 4-раскрасок.

Меньшим числом цветов этот граф раскрасить
правильно нельзя.

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

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

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

Алгоритм правильной раскраски

  • произвольной вершины
    графаприменим цвет 1.

  • Если вершины
    раскрашеныцветами,,
    то новой произвольно взятой вершинеприпишем
    цвет, не использованный при раскраске
    вершин из её окружения (т.е. инцидентных
    ей вершин).

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

    1. Планарность

      1. Плоские и
        планарные графы

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

  1. Граф называется плоским ,если его
    вершины – это точки лежащие на плоскости
    ,а рёбра – линии на плоскости , которые
    не пересекаются друг с другом.

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

  1. Плоские
    графы:

  1. Граф
    :

является планарным т.к. его можно
представить в виде плоского т.о.:

  1. Граф:

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

Задача о 3-х домах и 3-х колодцах.Имеются 3 дома 1,2,3 и 3 колодца 4,5,6 (граф):

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

      1. Грани плоского
        графа. Формула Эйлера

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

Таким образом, плоский граф разделяет
плоскость на грани.

  1. Границей грани будем считать
    множество вершин и рёбер, принадлежащей
    этой грани.

  1. Граф
    с 4-мя гранями. Плоский граф имеет
    единственную неограниченную грань
    (4). Такая грань называется внешней, а
    остальные грани — внутренними.

  1. Эйлера. Для всякого связного
    плоского графаверно равенство:

  1. -число граней плоского графа.

  1. Проведем
    по индукции по числу рёбер. Если
    ,
    то,
    т.е. теорема выполняется.

Предположим, что теорема выполняется
для всех графов с числом рёбер <=
,
т.е..
Добавим еще одно ребро. Если добавляемое
ребро соединяет существующие вершины,
то,,.
Тогда.
Если добавляемое ребро соединяет
существующую вершину с новой, то,,.
Тогда.

  1. Если
    связный планарный граф (),
    то.

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

.

  1. инепланарны.

  1. 1.
    Рассмотрим
    .
    Имеем,.
    Еслипланарен, то.
    Получили противоречие.

2. Рассмотрим
.
Имеем,.
В этом графе нет треугольников, значит,
если этот граф планарен, то в его плоской
укладке каждая грань ограничена по
крайней мере четырьмя ребрами.
Следовательно,или.
По формуле Эйлера,
отсюда.
Имеем.
Получили противоречие.

      1. Теорема
        Потрягина-Куратовского

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

  1. 2 графа называются гомеоморфными,
    если оба они могут быть получены из
    одного и того же графа подразбиением
    его рёбер.

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

Исторически первым критерием планарности
графов является критерий, доказанный
Потрягиным (1927) и Куратовским (1930)
независимо друг от друга.

  1. Потрягина-Куратовского:
    Граф планарен т.и.т.т., когда он не
    содержит подграфов, гомеоморфных К5или К3,3.

К5К3,3

Без доказательства.

      1. Алгоритм укладки
        графа на плоскости

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

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

Всё это вызвало появление алгоритмов,
которые не только проверяют граф на
планарность, но и строят его плоскую
укладку, если это возможно. Рассмотрим
один из этих алгоритмов.
.

Введем ряд определений.

  1. Пусть построена некоторая укладка
    подграфа
    графа.Сегментом относительно(или просто сегментом) будем называть
    подграф графаодного из двух видов:

  • Ребро
    такое, что,;

  • Компоненту связности графа
    ,
    дополненную всеми рёбрами графа,
    инцидентными ее вершинам (взятой
    компоненты), и концами этих рёбер.

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

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

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

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

Leave a Comment