Алексеев В.Б. Лекции по дискретной математике (1083733), страница 5

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

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

Отсюда 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) Пусть имеются корневые деревья D1, D2, …, Dm с корнями v1, v2, …, vm, Di = (Vi, Ei),Vi ∩ Vj = ∅ (i ≠ j).

Тогда граф D = (V, E), полученный следующим образом:V = V1 ∪ V2 ∪ … ∪ Vm ∪ {v} (v ∉ Vi, ∀i ), E = E1 ∪ E2 ∪ … ∪ Em ∪ {(v, v1), (v, v2), …,(v, vm)}и в котором выделена вершина v, называется корневым деревом.3) Только те объекты являются корневыми деревьями, которые можно построить согласно пунктам 1) и 2).17При таком определении D1,D2,…,Dm называются поддеревьями дерева D.v1D1…v2D2vmDm…vУтверждение.

Определения 1 и 2 эквивалентны.Определение 3. Упорядоченным корневым деревом называется корневое дерево, вкотором1) задан порядок поддеревьев и2) каждое поддерево Di является упорядоченным поддеревом.Дерево с одной вершиной также является упорядоченным поддеревом.Теорема 3. Число упорядоченных корневых деревьев с q рёбрами не превосходит 4q.Доказательство. Рассмотрим алгоритм обхода упорядоченного дерева, называемого«поиском в глубину». Этот обход описывается рекурсивно следующим образом:1) Начать с корня.

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

Таким образом, упорядоченных корневых деревьев с q рёбрами не больше, чем последовательностей из 0 и 1 длины 2q, а их число равно 22q = 4q. Теорема доказана.Изоморфизм корневых деревьев определяется так же, как и изоморфизм графов, но сдополнительным требованием: корень должен отображаться в корень. Для упорядоченныхкорневых деревьев также требуется сохранение порядка поддеревьев.Следствие. Число неизоморфных корневых деревьев с q рёбрами и число неизоморфных деревьев с q рёбрами не превосходит 4q.Доказательство.

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

Отсюда и из теоремы следует утверждение следствия. Следствиедоказано.§18. Геометрическая реализация графов.Теорема о реализации графов в трёхмерном пространстве.Определение. Пусть задан некоторый неориентированный граф G = (V, E). Пусть любой вершине vi графа G сопоставлена некоторая точка ai: vi → ai, ai ≠ aj (i ≠ j), а любому ребруe = (a, b) сопоставлена некоторая непрерывная кривая L, соединяющая точки ai и aj и не проходящая через другие точки ak (k ≠ i, j). Тогда если все кривые, сопоставленные рёбрам, не18имеют общих точек, кроме концевых, то говорят, что задана геометрическая реализацияграфа G.геометрическая реализация графа K 4не является геометрической реализацией графа K 4Теорема 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.a) Базис индукции: q = p – 1. Так как G — связный и q = p – 1, то согласно пункту 3теоремы 2 G — дерево, то есть, в G нет циклов.

Тогда r = 1. Отсюда p – q + r == p – (p – 1) + 1 = 2.b) Пусть для q: p – 1 ≤ q < q0 теорема справедлива. Докажем, что для q = q0 она такжесправедлива. Пусть G — связный граф с p вершинами и q0 рёбрами и пусть в егопланарной реализации r граней. Так как q0 > p – 1, то G — не дерево. Следовательно,в G есть цикл.

Пусть ребро e входит в цикл. Тогда к нему с двух сторон примыкаютразные грани. Удалим ребро e из G. Тогда две грани сольются в одну, а полученныйграф G1 останется связным. При этом получится планарная реализация графа G1 с pвершинами и q0 – 1 рёбрами и r – 1 гранями. Так как q0 – 1 < q0, то, по предположению индукции, для G1 справедлива формула Эйлера, то есть p – (q0 – 1) + (r – 1) = 2,откуда p – q0 + 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. Следствие доказано.19Следствие 2. Для любого выпуклого многогранника справедливо равенство p – q + r = 2,где p — число вершин, q — число рёбер, r — число граней.Доказательство. Пусть выпуклый многогранник M имеет p вершин, q рёбер и r граней.Пусть O — внутренняя точка многогранника.

Разместим сферу S с центром в точке O настолько большого радиуса, чтобы M целиком содержался в S. Рассмотрим центральное проектирование с центром в точке O, и спроектируем вершины и рёбра M на S. Тогда на S мыполучим геометрическую реализацию некоторого связного графа с p вершинами, q рёбрамии r гранями.

Отсюда согласно следствию 1 p – q + r = 2. Следствие 2 доказано.§20. Доказательство непланарности графов K5 и K3,3.Теорема Понтрягина-Куратовского (доказательство в одну сторону).Определение 1. Графом K5 называется граф с пятью вершинами, в котором каждая паравершин соединена ребром.K5Теорема 6. Граф K5 не планарен.Доказательство. Допустим, что для графа K5 существует планарная реализация. Так какграф K5 связен, то для этой планарной реализации справедлива формула Эйлера p – q + r = 2.Поскольку в графе K5 имеем p = 5 и q = 10, то число всех граней должно равняться r = 2 – p ++ q = 7.

Пусть грани занумерованы 1, 2, …, r и пусть при обходе i-ой грани по периметру (поеё краю) проходится qi рёбер. Так как при этом каждое ребро обходится дважды (оно являетrся стороной для двух граней), то ∑i =1 qi = 2q = 20 . Но в каждой грани не менее трёх сторон.Поэтому qi ≥ 3 для всех i. Отсюда∑ri =1qi ≥ 3r = 21 . Получаем 20 ≥ 21 — противоречие.

Зна-чит, для графа K5 не существует планарной реализации.Определение 2. Графом K3,3 называется граф с шестью вершинами a1, a2, a3, b1, b2, b3, вкотором каждая вершина ai соединена ребром с каждой вершиной bj и других рёбер нет.a1a2a3b1b2b3K3,3Теорема 7. Граф K3,3 не планарен.Доказательство. Допустим, что для графа K3,3 существует планарная реализация. Таккак граф K3,3 связен, то для этой планарной реализации справедлива формула Эйлера p – q ++ r = 2. Поскольку в графе K3,3 имеем p = 6 и q = 9, то число всех граней должно равнятьсяr = 2 – p + q = 5.

Так же, как в доказательстве предыдущей теоремы, получаем, чтоr∑i =1 qi = 2q = 18 , где qi — число сторон в i-ой грани. Но в графе K3,3 нет циклов длины 3. По-20этому в каждой грани не менее 4 сторон. Следовательно, qi ≥ 4 для всех i. Отсюдаr∑i=1 qi ≥ 4r = 20 . Получаем 18 ≥ 20 — противоречие. Значит, для графа K3,3 не существуетпланарной реализации.Определение 3. Подразделением ребра (a, b) называется операция, состоящая в следующих действиях:1) удаление (a, b),2) добавление новой вершины c,3) добавление рёбер (a, c) и (c, b).Определение 4. Граф H называется подразделением графа G, если H можно получить изG путём конечного числа подразделений своих рёбер.Определение 5.

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

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