Эйлеровы циклы. Теор. о сущ. эйлерова цикла. Уникурсальные графы. Гамильтоновы циклы.

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

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

Док-во

1. Необх. Имеется связный эйл. граф. Док-ть, что степени всех вершин чётные. Будем изначально считать степени всех вершин = 0. Будем подсчитывать степени всех вершин, обходя граф по эйлерову циклу. По завершении обхода графа мы побываем в каждой вершине, потому что граф связный; мы обойдём все рёбра, потому что цикл эйлеров; каждый проход через вершину увеличивает её степень на 2. Значит по завершении обхода степени всех вершин подсчитана точно и они кратны двум.

2. Дост. Дан связный граф, степени вершин чётны. Док-ть, что граф эйлеров. Док-во фактически даёт алгоритм построения эйлерова цикла.

Выберем произв. вершину графа. Начнём из неё строить цепь, проходя по каждому ребру ровно 1 раз. Эта цепь незбежно закончится в нач. вершине, замкнувшись в цикл.

Рассмотрим полученный цикл. Он обладает след. св-ом: все рёбра, входящие в него ровно 1 раз. Если в него вошли все рёбра графа, то этот цикл эйлеров и док-во звершено.

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

Очевидно, что данная процедура конечна. В результате получим за конечное число шаговцикл, кот. будет обладать след. св-ми: 1) все вошедшие в этот цикл рёбра будут входить в него 1 раз; 2) в этот цикл входят все рёбра графа. Т.о. получим эйлеров цикл. Ч. Т. Д.

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

Теор. 2 (критерий уникурсальности): Граф уникурсален т. и т. т., к. он явл. либо эйлеровым либо содержит ровно 2 вершины нечётной степени.

Опр. 3: Цикл, содержащий все вершины графа по одному разу назыв. гамильтоновым. Граф, в кот. есть этот цикл назыв. гамильтоновым.

№8. Плоские и планарные графы. Теор. Понтрягина-Куратовского. Полный граф. Двудольный граф. Теор. Кёнига.

Опр. 1: Граф назыв. плоским, если он изображён так, что его рёбра не пересекаются. Плоский граф или граф, кот. можно перерисовать как плоский, назыв. планарным.

Теор. 1 (Понтрягина-Куратовского, критерий планарности): Граф планарен т. и т. т., к. он не содержит в качестве своей части графов К_5,5 и К_3,3 (быть может с доп. вершинами степени 2).

Зам. 1: теор. неудобна на практике.

Опр. 2: Граф назыв. полным, если каждые две вершины его смежны.

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

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

Опр. 5: В плоском графе часть плоскости, ограниченная простым циклом и обладающая св-ом: любые 2 точки этой части плоскости можно соединить непрерывной линией, не содержащей точек, принадлежащих диаграмме графа; назыв. гранью. Плоскость, окруж. плоский граф назыв. внеш. гранью. Число различных граней обознач. v(G) (или r(G)).

Теор. 2 (Кёнига, критерий двудольности): Граф явл. двудольным т. и т. т., к. все его циклы чётные.

Док-во:

1) Необх. Если граф двудольный, то все циклы чётны – это оч.видно.

2) Дост. Дан граф. Все циклы чётны, док-ть, что он двудольный.

Возьмём любую вершину, найдём кратчайшие цепи, соединяющие нашу вершину, со всеми остальными. Заметим, что если имеется цепь (v₀, v_i) чётной длины, то все остальные цепи, соединяющие эти вершины, имеют тоже чётную длину. Аналогично, если цепь (v₀, v_i) нечёт. длины, то все остальные – нечётные.

Разобьём все вершины графа на 2 доли. В 1-ю включим вершину v₀ и все вершины, отстоящие от неё на чётные расстояния; во 2-ю долю – все вершины, отстоящие от v₀ на нечётные расстояния. Док-м, что получили двудольный граф. Док-м, что две вершины одной доли не могут быть соединены ребром. Пусть это вершины v_i и v_j. Пусть сущ. ребро их соединяющее. Но сущ. цепи (v_0, v_i) и (v₀, v_j). Сумма длин цепей чётна, а плюс это ребро, то нечётна, что не есть хорошо. Ч. Т. Д.

№9 Теор. Эйлера о связном планарном графе. Следствия из теор.

Теор. 1 (Эйлера о связном планарном графе): В любом связном планарном графе выполняется соотн.: p-q+r =2.

Док-во.

ММИ по числу рёбер.

1) Базис – пусть q=0 => р=1, r =1. Соотн. выполн.

2) Индуктивное допущение: предположим, что данное допущение верно для данноо связного планарного графа с числом рёбер q, т.е. выполняется p-q+r = 2.

3) Добавим в граф одно новое ребро. Теоретически возможны 3 случая:

а) новое ребро соединяет две сущ. вершины. Имеем: p`=p, q`=q+1, r`=r+1. p`-q`+r`=2.

б) новое ребро соединяет одну сущ. вершину с одной новой. p`=p+1, q`=q+1, r`=r. p`-q`+r`=2.

в) новое ребро соединяет две новые вершины. В этом случае разбивается на две компоненты связности и мы выходим за рамки условия теор. Ч. Т. Д.

Сл. 1: Для любого связного планарного графа с числом вершин >3, выполняется q≤3p-6.

Док-во. Так как по условию q ≥3, то получаем 2q≥3r и r ≤2q/k. Из формулы Эйлера r = 2-p+q. Отсюда 2-p+q ≤2q/3. Далее (3-2)q ≤3(p-2) и q ≤ [3/(3-2)](p-2). Ч. Т. Д.

Сл. 2: Графы К_3,3 и К₅ непланарны.

Док-во. Допустим, что для графа K_3,3 существует планарная реализация. Так как граф K_3,3 связан, то для этой планарной реализации справедлива формула Эйлера p-q+r =2. Поскольку в графе K_3,3 имеем p=6 и q=9, то число всех граней должно равняться r =2-p+q=5. Получаем, что å_{i = 1}^r q_i = 2q = 18, где q_i - число сторон в i-ой грани. Но в графе K_3,3 нет циклов длины 3. Поэтому в каждой грани не менее 4 сторон. Следовательно, q_i³4 для всех i. Отсюда q_i ³ 4r = 20. Получаем 18³20 - противоречие. Значит для графа K_3,3 не существует планарной реализации.

Допустим, что для графа K₅ существует планарная реализация. Так как граф K₅ связен, то для этой планарной реализации справедлива формула Эйлера p-q+r =2. Поскольку в графе K₅ имеем p=5 и q=10, то число всех граней должно равняться r =2-p+q=7. Пусть грани занумерованы 1, 2,..., r и пусть при обходе i-ой грани по периметру (по ее краю) проходится q_i ребер. Так как при этом каждое ребро проходится дважды (оно является стороной для двух граней), то q_i=2q=20. Но в каждой грани не менее 3 сторон. Поэтому q_i ³ 3 для всех i. Отсюда q_i ³ 3r=21. Получаем 20³21 - противоречие. Значит для графа K₅ не существует планарной реализации.

Сл. 3: В любом планарном графе сущ. вершина, степень кот. не превосх. 5.

Док-во. Пусть G - планарный граф с p вершинами и q ребрами. Тогда q£3(p-2)<3p. Пусть d_min- минимальная степень вершин в G. Тогда получаем 6p>2q= ³pd_min. Отсюда d_min<6, то есть d_min£5.

---

Дата добавления: 2015-07-20