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

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

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

Доказательство. Пусть выпуклый многогранник M имеет p вершин, q рёбер и r граней. Пусть O — внутренняя точка многогранника. Разместим сферу S с центром в точке O настолько большого радиуса, чтобы M целиком содержался в S. Рассмотрим центральное проектирование с центром в точке O, и спроектируем вершины и рёбра M на S. Тогда на S мы получим геометрическую реализацию некоторого связного графа с p вершинами, q рёбрами и r гранями. Отсюда согласно следствию 1 p – q + r = 2. Следствие 2 доказано.

§20. Доказательство непланарности графов K₅ и K_3,3. Теорема Понтрягина-Куратовского (доказательство в одну
сторону)

Определение 1. Графом K₅ называется граф с пятью вершинами, в котором каждая пара вершин соединена ребром.

Теорема 6. Граф K₅ не планарен.

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

Определение 2. Графом K_3,3 называется граф с шестью вершинами a₁, a₂, a₃, b₁, b₂, b₃, в котором каждая вершина a_i соединена ребром с каждой вершиной b_j и других рёбер нет.

Теорема 7. Граф K_3,3 не планарен.

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

Определение 3. Подразделением ребра (a, b) называется операция, состоящая в следующих действиях:

1. удаление (a, b),

2. добавление новой вершины c,

3. добавление рёбер (a, c) и (c, b).

Определение 4. Граф H называется подразделением графа G, если H можно получить из G путём конечного числа подразделений своих рёбер.

Определение 5. Два графа называются гомеоморфными, если существуют их подразделения, которые изоморфны.

Теорема 8 (Понтрягина-Куратовского). Граф является планарным тогда и только тогда, когда он не содержит ни одного подграфа, гомеоморфного графам K₅ или K_3,3.

Доказательство. Необходимость. Пусть G — планарный. Допустим, что он содержит подграф G₁, гомеоморфный графу K₅ или K_3,3. Рассмотрим планарную реализацию графа G. Удалив лишние вершины и рёбра, мы получим планарную реализацию подграфа G₁. Но G₁ геометрически — это граф K₅ или K_3,3 с точками на рёбрах. Если проигнорировать эти точки, то мы получим планарную реализацию графа K₅ или K_3,3. Но это невозможно в силу теорем 1 и 2. Необходимость доказана.

Достаточность без доказательства.

§21. Теорема о раскраске планарных графов в пять цветов

Лемма 1. Для любой геометрической реализации на плоскости связного планарного графа с q рёбрами выполняется равенство:

,

где суммирование ведётся по всем граням (включая внешнюю).

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

Теорема 9. Если в связном планарном графе G = (V, E) с p вершинами и q рёбрами, отличном от дерева, нет циклов длины меньше k
(k  3), то .

Доказательство. Так как по условию q_i  k, то из леммы получаем 2q  kr и . Из формулы Эйлера r = 2 – p + q. Отсюда . Далее (k – 2)q  k(p – 2) и . Теорема доказана.

Следствие. В любом связном планарном графе G = (V, E) без петель и кратных рёбер с p  3 вершинами и q рёбрами справедливо неравенство: q  3( p – 2).

Определение 1. Подмножество V₁  V вершин графа G = (V, E) называется независимым, если никакие две вершины из V₁ не соединяются ребром.

Определение 2. Пусть есть некоторое множество C={C₁,C₂,…,C_m} — множество цветов. Тогда раскраской графа G = (V, E) (вершинной) называется любое отображение φ: V  C. Раскраска называется правильной, если для любого цвета вершины этого цвета образуют независимое множество.

Лемма 2. В планарном графе без петель и кратных рёбер существует вершина v:

deg v  5.

Доказательство. Пусть G — планарный граф с p вершинами и q рёбрами. Пусть в G нет вершин степени 0 и 1. Тогда q  3(p – 2) < 3p. Пусть d_min — минимальная степень вершин в G. Тогда получаем

.

Отсюда d_min < 6, то есть d_min  5. Лемма доказана.

Теорема 10. Вершины любого планарного графа можно правильно раскрасить в не более чем 5 цветов.

Доказательство. Проведём индукцию по числу вершин p.

1. Базис индукции: p = 1 — очевидно.

2. Пусть для p < p₀ утверждение справедливо и пусть G = (V, E) — планарный граф с |V| = p₀. Согласно лемме 2 в G есть вершина v степени не более 5. Рассмотрим укладку на плоскости графа G без пересечения рёбер. Удалим из G вершину v и все инцидентные ей рёбра. Получим планарный граф G₁ с числом вершин p₀ – 1. По предположению индукции его вершины можно правильно раскрасить в 5 цветов C₁, C₂, C₃, C₄, C₅. Пусть в G вершина v смежна с v₁, v₂, …, v_k, где k  5. Возможны два случая:

1. Среди цветов вершин v₁, v₂, …, v_k в G нет цвета C_i (1  i  5). Тогда вершине v припишем цвет C_i и получим правильную раскраску графа G в 5 цветов.

2. Степень вершины v равна 5 и среди вершин v₁, v₂, …, v₅ в G₁ есть все 5 цветов. Без ограничения общности будем считать, что в укладке графа G рёбра (v, v₁), (v, v₂), (v, v₃), (v, v₄), (v, v₅) выходят из v в порядке по часовой стрелке и что C (v_i) = C_i, i = 1, …, 5. Пусть A — множество всех вершин в G₁, до которых можно дойти из v₁ по рёбрам графа G₁, используя только вершины цветов C₁ и C₃. Возможны два варианта:

   1. v₃A. Тогда в A поменяем цвета C₁  C₃, C₃  C₁. Так как вершины из A не смежны с другими вершинами цветов C₁ и C₃, то останется правильная раскраска и среди v₁, v₂, v₃, v₄, v₅ не будет цвета C₁. Тогда вершине v припишем цвет C₁.

   2. v₃A. Это значит, что в A есть цепь из v₁ в v₃, все вершины которой имеют цвета C₁ и C₃. Эта цепь вместе с рёбрами (v₃, v) и (v, v₁) образует цикл в G, причём вершины v₂ и v₄ лежат по разные стороны от этого цикла. Это значит, что из v₂ нельзя пройти в v₄ в графе A только по вершинам цветов C₂ и C₄. Пусть B — множество всех вершин в G, до которых можно дойти из v₂ по рёбрам графа G, используя только вершины цветов C₂ и C₄. Тогда v₄B и далее поступаем как в i).

В любом случае вершины графа G можно правильно раскрасить в не более чем 5 цветов, и теорема доказана.

Глава III. Основы теории
управляющих систем

§22. Схемы из функциональных элементов. Реализация функций алгебры логики схемами

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

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

Определение 3. В ациклическом орграфе глубиной вершины v называется максимальное число дуг в ориентированном пути из какого-нибудь истока в вершину v.

Если в ациклическом орграфе есть дуга (v₁, v₂), то глубина v₂ больше глубины v₁.

Определение 4. Орграф называется упорядоченным, если для каждой вершины v_i, в которую входит k_i дуг, задан порядок этих дуг.

Определение 5. Систему Б = {g₁, g₂, …, g_m}, где все g_i — функции алгебры логики, будем называть базисом функциональных элементов.

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

1) каждому истоку приписана некоторая переменная, причем разным истокам приписаны разные переменные (истоки при этом называются входами схемы, а приписанные им переменные — входными переменными);

2) каждой вершине, в которую входят k  1 дуг, приписана функция из базиса Б, зависящая от k переменных (вершина с приписанной функцией при этом называется функциональным элементом);

3) некоторые вершины выделены как выходы (истоки одновременно могут являться выходами).

Индукцией по глубине q вершины v определяется функция f_v, реализуемая в данной вершине. Если q = 0, то есть v — исток, и v приписана переменная x_i, то f_v  x_i. Пусть реализуемые функции уже определены для всех вершин глубины меньшей, чем q₀, и глубина v равна q₀. Пусть в v входят дуги e₁, e₂, …, e_k из вершин v₁, v₂, …, v_k и в них реализуются функции f₁, f₂, …, f_k. Пусть вершине v приписана функция
g (x₁, …, x_k). Тогда в v реализуется функция f_v = g (f₁, f₂, …, f_k).

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

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