20. Деревья.

Дерево — связный граф без циклов (=> и без множественных рёбер, и без петель).

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

Для дерева верно:

1) для каждой пары разл. вершин существует единственный путь, их соединяющий;

2) удаление любого ребра из T приводит к появлению 2-х компонент связности.

3) |E| = |V| - 1.

--------

Корневое дерево — дерево (T,V*), у к-рого есть особая вершина (V*), отличающаяся от остальных.

Лист в корневом дереве — вершина, валентность к-рой = 1, не совпадающая с V*.

Вершина решения или внутренняя вершина — вершина, отличная от листа и V*.

Уровень вершины v для корневого дерева — длина пути, соединяющего v с V*.

--------

Двоичные деревья (L,S,R), где L и R — двоичные деревья, а S содержит только V*.

Деревья юзают для сортировки (дерево сортировки заполняют, а потом считывают в список).

Планарные

Граф — плоский, если его вершины лежат на плоскости, а рёбра — линии или дуги на плоскости — не пересекаются.

Граф — планарный, если он изоморфен плоскому.

Ф-ла Эйлера: |F| = |E|-|V|+2

|E| — кол-во рёбер

|V| — кол-во вершин

|F| — кол-во граней

Очевидно выполняется для деревьев.

-P: (индукция по числу рёбер n)

1) Пусть n=0 — одна вершина v. Рёбер — 0; грань — одна.

2) Предположим, что верно для |E| < n;

3) Если Г — дерево (тогда выполняется);

Если Г — не дерево, то у него есть цикл. Уберём в этом цикле ребро. По шагу 2 выполняется |F| = |E|-|V|+2. Добавим ребро. Равенство сохранится, т.к. грань++, ребро++: |F+1| = |E+1|-|V|+2

--------

K_(3,3) и K_5 непланарны (идёт отдельным вопросом)

--------

Если граф Г имеет подграфом K_(3,3) или K_5, то он непланарен.

Для того, чтобы конечный граф Г имел планарную реализацию, необходимо и достаточно, чтобы любой его подграф не был гомеоморфен ни одному из графов K_(3,3) и K_5.

Графы Г1 и Г2 гомеоморфны, если существуют их подразделения, к-рые изоморфны.

Подразделение — построение нового графа, мн-во вершин к-рого = V U {v} и мн-во рёбер = {(vi,v),(vj,v)} U E \ {vi,vj}, v — новая вершина, vi,vj — старые.

Vi*-----*Vj ->

Vi*---*(v)----*Vj

--------

Для определения гомеоморфизма графов из них можно последовательно удалять 2-х валентные вершины.

--------

Св-ва:

1)Г — связный планарный граф, без петель и множественных рёбер =>

|E| <= 3|V| - 6.

-P:

3|F| <= 2|E|, но |F| = 2 - |V| + |E| => 3(2 - |V| + |E|) <= 2|E| => |E| <= 3|V| - 6.

2) В любом планарном графе существует вершина, валентность к-рой <= 5.

-P: (от противного)

Пусть для всех Vi € V. Сигма(валентность)(Vi) >= 6. => 6|V| <= SUM(Vi € V)(Сигма(Vi)) = 2|E|. => 3|V| <= |E|

Из св-ва (1) =>3|V| <= 3|V| - 6. Что неверно. => неверно предположение. => верно св-во.

K5, K3,3

Непланарность:

K33:

Предположим, что K33 — планарный. Разбивает пл-сть, на к-рой лежит, на |F| граней. Каждая грань отсечена замкнутой последовательностью рёбер, состоящей минимум из 4-х рёбер. С другой стороны, каждое ребро грани представляет собой часть границы раздела двух граней.

=> 2|E| >= 4|F|

По т. Эйлера, 2|E| >= 4(|E|-|V|+2)

2*9 >= 4(9-6+2)

18 >= 20 неверно => предположение неверно => K33 не является планарным

K5 (пентограмма в пентакле):

Предположим, что K5 — планарный. Разбивает пл-сть, на к-рой лежит, на |F| граней. Каждая грань отсечена замкнутой последовательностью рёбер, состоящей минимум из 3-х рёбер. С другой стороны, каждое ребро грани представляет собой часть границы раздела двух граней.

=> 2|E| >= 3|F|

2|E| >= 3(|E|-|V|+2)

2*10 >= 3(10-5+2)

20 >= 21 неверно => предположение неверно => K5 не является планарным.