Алексеев В.Б. Лекции по дискретной математике. ВМК, 2004. Электронный ресурс (1083731), страница 5

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 5)

Определение 17. Путь называется простым циклом, если v₀ = v_n и вершины не повторяются.

Определение 18. Граф G = (V, E) называется связным, если для любых вершин v_i, v_j  V (v_i  v_j) существует путь из v_i в v_j.

Рассмотрим отношение v_i  v_j существования пути из v_i в v_j. Оно

1. симметрично, так как (v_i  v_j)  (v_j  v_i),

2. транзитивно, так как (v_i  v_j) & (v_j  v_k)  (v_i  v_k),

3. рефлексивно, так как i (v_i  v_i).

Таким образом, получено, что v_i  v_j — отношение эквивалентности и множество вершин разбивается на конечное число классов эквивалентности: V  V₁  V₂  …  V_k, V_i  V_j =   i  j. При этом граф G разбивается на связные подграфы, которые называются компонентами связности.

§16. Деревья. Свойства деревьев.

Определение 1. Деревом называется связный граф без циклов.

Определение 2. Подграф G₁ = (V₁, E₁) графа G = (V, E), называется остовным деревом в графе G = (V, E), если G₁ = (V₁, E₁) — дерево и V₁ = V.

Лемма 1. Если граф G = (V, E) связный и ребро (a, b) содержится в некотором цикле в графе G, то при выбрасывании из графа G ребра (a, b) снова получится связный граф.

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

Теорема 1. Любой связный граф содержит хотя бы одно остовное дерево.

Доказательство. Если в G нет циклов, то G является искомым остовным деревом. Если в G есть циклы, то удалим из G какое-нибудь ребро, входящее в цикл. Получится некоторый подграф G₁. По лемме 1 G₁ — связный граф. Если в G₁ нет циклов, то G₁ и есть искомое остовное дерево, иначе продолжим этот процесс. Процесс должен завершиться, так как E — конечное множество. Теорема доказана.

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

Доказательство. Рассмотрим произвольный связный граф G = (V, E). Пусть u  V, v  V, (u, v)  E. Так как G — связный граф, то в нём есть путь из v в u. Тогда в G есть и простая цепь C из v в u. Поэтому в полученном графе есть цикл C, (u, v), v. Лемма доказана.

Лемма 3. Пусть в графе G = (V, E) p вершин и q рёбер. Тогда в G не менее p – q связных компонент. Если при этом в G нет циклов, то G состоит ровно из p – q связных компонент.

Доказательство. Пусть к некоторому графу H, содержащему вершины u и v, добавляется ребро (u, v). Тогда если u и v лежат в разных связных компонентах графа H, то число связных компонент уменьшится на 1. Если u, v лежат в одной связной компоненте графа H, то число связных компонент не изменится. В любом случае, число связных компонент уменьшается не более чем на 1. Значит, при добавлении q рёбер число связных компонент уменьшается не более чем на q. Так как граф G получается из графа G₁ = (V, ) добавлением q рёбер, то в G не менее p – q связных компонент. Пусть теперь в G нет циклов, и пусть в процессе получения G из G₁ добавляется ребро (u, v). Если бы u, v лежали уже в одной связной компоненте, то в G, согласно лемме 2, возникал бы цикл. Следовательно, u, v лежат в разных связных компонентах и при добавлении ребра (u, v) число связных компонент уменьшается ровно на 1. Тогда G состоит ровно из p – q связных компонент. Лемма доказана.

Теорема 2 (о различных определениях дерева). Следующие пять определений эквивалентны (p — число вершин, q — число рёбер):

1. G — дерево;

2. G — без циклов и q = p – 1;

3. G — связный граф и q = p – 1;

4. G — связный граф, но при удалении любого ребра становится несвязным;

5. G — без циклов, но при добавлении любого ребра на тех же вершинах появляется цикл.

Доказательство. Докажем следующие переходы: 1)  2)  3)   4)  5)  1), откуда будет следовать, что из любого условия вытекает любое другое.

1)  2): так как G — связный граф и G не содержит циклов, то
p – q = 1 по лемме 3. Отсюда q = p – 1.

2)  3): по лемме 3 в G число связных компонент равно p – q = 1, то есть G — связный граф.

3)  4): при удалении одного ребра p – q = 2. Тогда по лемме 3 число связных компонент не менее чем p – q = 2.

4)  5): если G имеет цикл, то согласно лемме 1 можно выбросить одно ребро так, что граф останется связным. Согласно лемме 2, если добавить любое новое ребро к связному графу G на тех же вершинах, то появится цикл.

5)  1): если G не связный граф и вершины u, v лежат в разных связных компонентах графа G, то добавление к G ребра (u, v), очевидно, не порождает циклов, что противоречит 5). Отсюда следует, что
G — связный граф. Теорема доказана.

§17. Корневые деревья. Верхняя оценка их числа

Определение 1. Любое дерево, в котором выделена одна вершина, называемая корнем, называется корневым деревом.

Определение 2. 1) Граф, состоящий из одной вершины, которая выделена, называется корневым деревом.

2) Пусть имеются корневые деревья D₁,D₂,…,D_m с корнями v₁,v₂,…
…, v_m, D_i = (V_i, E_i), V_i  V_j =  (i  j). Тогда граф D = (V, E), полученный следующим образом:

V = V₁  V₂  …  V_m  {v} (v  V_i, i ),
E = E₁  E₂  …  E_m  {(v, v₁), (v, v₂), …,(v, v_m)}

и в котором выделена вершина v, называется корневым деревом.

3) Только те объекты являются корневыми деревьями, которые можно построить согласно пунктам 1) и 2).

При таком определении D₁,D₂,…,D_m называются поддеревьями дерева D.

Утверждение. Определения 1 и 2 эквивалентны.

Определение 3. Упорядоченным корневым деревом называется корневое дерево, в котором

1. задан порядок поддеревьев и

2. каждое поддерево D_i является упорядоченным поддеревом.

Дерево с одной вершиной также является упорядоченным поддеревом.

Теорема 3. Число упорядоченных корневых деревьев с q рёбрами не превосходит 4^q.

Доказательство. Рассмотрим алгоритм обхода упорядоченного дерева, называемого «поиском в глубину». Этот обход описывается рекурсивно следующим образом:

1. Начать с корня. Пока есть поддеревья выполнять:

2. перейти в корень очередного поддерева, обойти это поддерево «в глубину».

3. Вернуться в корень исходного поддерева.

В результате обход «в глубину» проходит по каждому ребру дерева ровно 2 раза: один раз при переходе в очередное поддерево, второй раз при возвращении из этого поддерева. В соответствии с обходом «в глубину» будем строить последовательность из нулей и единиц, записывая на каждом шаге нуль или единицу, причём нуль будем записывать, если происходит переход в очередное поддерево, а единицу, если мы возвращаемся из поддерева. Получим последовательность из 0 и 1 длины 2q, которую назовём кодом дерева. По этому коду однозначно восстанавливается дерево, поскольку каждый очередной разряд однозначно указывает, начинать ли строить новое очередное поддерево или возвращаться на ярус ближе к корню. Таким образом, упорядоченных корневых деревьев с q рёбрами не больше, чем последовательностей из 0 и 1 длины 2q, а их число равно 2^2q = 4^q. Теорема доказана.

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

Следствие. Число неизоморфных корневых деревьев с q рёбрами и число неизоморфных деревьев с q рёбрами не превосходит 4^q.

Доказательство. Выделяя в неизоморфных деревьях по одной вершине, мы получим неизоморфные корневые деревья. Упорядочивая поддеревья в неизоморфных корневых деревьях, мы получим различные упорядоченные корневые деревья. Поэтому число неизоморфных деревьев с q рёбрами не превосходит числа неизоморфных корневых деревьев с q рёбрами, которое, в свою очередь, не превосходит числа различных упорядоченных корневых деревьев с q рёбрами. Отсюда и из теоремы следует утверждение следствия. Следствие доказано.

§18. Геометрическая реализация графов. Теорема о реализации графов в трёхмерном пространстве

Определение. Пусть задан некоторый неориентированный граф
G = (V, E). Пусть любой вершине v_i графа G сопоставлена некоторая точка a_i: v_i  a_i, a_i  a_j (i  j), а любому ребру e = (a, b) сопоставлена некоторая непрерывная кривая L, соединяющая точки a_i и a_j и не проходящая через другие точки a_k (k  i, j). Тогда если все кривые, сопоставленные рёбрам, не имеют общих точек, кроме концевых, то говорят, что задана геометрическая реализация графа G.

Теорема 4. Для любого графа существует его реализация в трёхмерном пространстве.

Доказательство. Возьмём в пространстве любую прямую l и разместим на ней все вершины графа G. Пусть в G имеется q рёбер. Проведём связку из q различных полуплоскостей через l. После этого каждое ребро графа G можно изобразить линией в своей полуплоскости и они, очевидно, не будут пересекаться. Теорема доказана.

§19. Планарные (плоские) графы. Формула Эйлера

Определение 1. Граф называется планарным, если существует его геометрическая реализация на плоскости.

Определение 2. Если имеется планарная реализация графа и мы «разрежем» плоскость по всем линиям этой планарной реализации, то плоскость распадётся на части, которые называются гранями этой планарной реализации (одна из граней бесконечна, она называется внешней гранью).

Теорема 5 (формула Эйлера). Для любой планарной реализации связного планарного графа G = (V, E) с p вершинами, q рёбрами и r гранями выполняется равенство: p – q + r = 2.

Доказательство. Докажем теорему при фиксированном p индукцией по q. Так как G — связный граф, то q  p – 1.

1. Базис индукции: q = p – 1. Так как G — связный и q = p – 1, то согласно пункту 3 теоремы 2 G — дерево, то есть, в G нет циклов. Тогда r = 1. Отсюда p – q + r = p – (p – 1) + 1 = 2.

2. Пусть для q: p – 1  q < q₀ теорема справедлива. Докажем, что для q = q₀ она также справедлива. Пусть G — связный граф с p вершинами и q₀ рёбрами и пусть в его планарной реализации r граней. Так как q₀ > p – 1, то G — не дерево. Следовательно, в G есть цикл. Пусть ребро e входит в цикл. Тогда к нему с двух сторон примыкают разные грани. Удалим ребро e из G. Тогда две грани сольются в одну, а полученный граф G₁ останется связным. При этом получится планарная реализация графа G₁ с p вершинами и q₀ – 1 рёбрами и r – 1 гранями. Так как q₀ – 1 < q₀, то, по предположению индукции, для G₁ справедлива формула Эйлера, то есть p – (q₀ – 1) + (r – 1) = 2, откуда p – q₀ + r = 2. Что и требовалось доказать.

Следствие 1. Формула Эйлера справедлива и для геометрической реализации связных графов на сфере.

Доказательство. Пусть связный граф G с p вершинами и q рёбрами реализован на сфере S так, что число граней равно r. Пусть точка A на сфере не лежит на линиях этой геометрической реализации. Пусть
P — некоторая плоскость. Поставим сферу S на плоскость P так, чтобы точка A была самой удалённой от плоскости. Спроектируем S на P центральным проектированием с центром в точке A. Тогда на плоскости P мы получим геометрическую реализацию связного графа с p вершинами и q рёбрами, причём число граней будет равно r (грань на сфере, содержащая A, отображается на внешнюю грань на плоскости). По теореме получаем p – q + r = 2. Следствие доказано.

Следствие 2. Для любого выпуклого многогранника справедливо равенство p – q + r = 2, где p — число вершин, q — число рёбер, r — число граней.

Характеристики

Список файлов лекций