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

Два графа называются гомеоморфными, если существуют их подразделения, которые изоморфны.Теорема 8 (Понтрягина-Куратовского). Граф является планарным тогда и только тогда, когда он не содержит ни одного подграфа, гомеоморфного графам K5 или K3,3.Доказательство. Необходимость. Пусть G — планарный. Допустим, что он содержитподграф G1, гомеоморфный графу K5 или K3,3. Рассмотрим планарную реализацию графа G.Удалив лишние вершины и рёбра, мы получим планарную реализацию подграфа G1.

Но G1геометрически — это граф K5 или K3,3 с точками на рёбрах. Если проигнорировать эти точки,то мы получим планарную реализацию графа K5 или K3,3. Но это невозможно в силу теорем 1и 2. Необходимость доказана.Достаточность без доказательства.§21. Теорема о раскраске планарных графов в пять цветов.Лемма 1. Для любой геометрической реализации на плоскости связного планарного графа с q рёбрами выполняется равенство:r∑qi =1i= 2q ,где суммирование ведётся по всем граням (включая внешнюю).Доказательство. Равенство следует из того, что у каждого ребра две стороны и присуммировании qi каждое ребро учитывается дважды: либо оно входит в границы двух соседних граней, либо оно дважды учитывается в одной грани.

Лемма доказана.Теорема 9. Если в связном планарном графе G = (V, E) с p вершинами и q рёбрами, отличном от дерева, нет циклов длины меньше k (k ≥ 3), то q ≤ k −k 2 ( p − 2) .Доказательство. Так как по условию qi ≥ k, то из леммы получаем 2q ≥ kr и r ≤2qk. Изформулы Эйлера r = 2 – p + q. Отсюда 2 − p + q ≤ 2kq . Далее (k – 2)q ≤ k(p – 2) и q ≤ k −k 2 ( p − 2) .Теорема доказана.Следствие. В любом связном планарном графе G = (V, E) без петель и кратных рёбер сp ≥ 3 вершинами и q рёбрами справедливо неравенство: q ≤ 3( p – 2).Определение 1.

Подмножество V1 ⊆ V вершин графа G = (V, E) называется независимым, если никакие две вершины из V1 не соединяются ребром.Определение 2. Пусть есть некоторое множество C = {C1, C2, …, Cm} — множествоцветов. Тогда раскраской графа G = (V, E) (вершинной) называется любое отображениеφ: V → C. Раскраска называется правильной, если для любого цвета вершины этого цвета образуют независимое множество.Лемма 2. В планарном графе без петель и кратных рёбер существует вершина v:deg v ≤ 5.21Доказательство. Пусть G — планарный граф с p вершинами и q рёбрами.

Пусть в G нетвершин степени 0 и 1. Тогда q ≤ 3(p – 2) < 3p. Пусть dmin — минимальная степень вершин вG. Тогда получаемp6 p > 2q = ∑ deg vi ≥ pd min .i =1Отсюда dmin < 6, то есть dmin ≤ 5. Лемма доказана.Теорема 10. Вершины любого планарного графа можно правильно раскрасить в не более чем 5 цветов.Доказательство. Проведём индукцию по числу вершин p.1) Базис индукции: p = 1 — очевидно.2) Пусть для p < p0 утверждение справедливо и пусть G = (V, E) — планарный граф с|V| = p0. Согласно лемме 2 в G есть вершина v степени не более 5. Рассмотрим укладку наплоскости графа G без пересечения рёбер.

Удалим из G вершину v и все инцидентные ейрёбра. Получим планарный граф G1 с числом вершин p0 – 1. По предположению индукцииего вершины можно правильно раскрасить в 5 цветов C1, C2, C3, C4, C5. Пусть в G вершина vсмежна с v1, v2, …, vk, где k ≤ 5. Возможны два случая:a) Среди цветов вершин v1, v2, …, vk в G нет цвета Ci (1 ≤ i ≤ 5). Тогда вершине vприпишем цвет Ci и получим правильную раскраску графа G в 5 цветов.b) Степень вершины v равна 5 и среди вершин v1, v2, …, v5 в G1 есть все 5 цветов.Без ограничения общности будем считать, что в укладке графа G рёбра (v, v1),(v, v2), (v, v3), (v, v4), (v, v5) выходят из v в порядке по часовой стрелке и чтоC (vi) = Ci, i = 1, …, 5.

Пусть A — множество всех вершин в G1, до которых можнодойти из v1 по рёбрам графа G1, используя только вершины цветов C1 и C3. Возможны два варианта:i) v3∉A. Тогда в A поменяем цвета C1 → C3, C3 → C1. Так как вершины из A несмежны с другими вершинами цветов C1 и C3, то останется правильная раскраска и среди v1, v2, v3, v4, v5 не будет цвета C1. Тогда вершине v припишемцвет C1.ii) v3∈A. Это значит, что в A есть цепь из v1 в v3, все вершины которой имеютцвета C1 и C3. Эта цепь вместе с рёбрами (v3, v) и (v, v1) образует цикл в G,причём вершины v2 и v4 лежат по разные стороны от этого цикла.

Это значит,что из v2 нельзя пройти в v4 в графе A только по вершинам цветов C2 и C4.Пусть B — множество всех вершин в G, до которых можно дойти из v2 порёбрам графа G, используя только вершины цветов C2 и C4. Тогда v4∉B и далее поступаем как в i).В любом случае вершины графа G можно правильно раскрасить в не более чем 5 цветов,и теорема доказана.22Глава III. Основы теории управляющих систем.§22. Схемы из функциональных элементов.Реализация функций алгебры логики схемами.Определение 1. Вершины орграфа, в которые не входит ни одной дуги, называютсяистоками.Определение 2.

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

Орграф называется упорядоченным, если для каждой вершины vi, в которую входит ki дуг, задан порядок e1 , e2 ,!, eki этих дуг.Определение 5. Систему Б = {g1, g2, …, gm}, где все gi — функции алгебры логики, будем называть базисом функциональных элементов.Определение 6. Схемой из функциональных элементов в базисе Б называется ациклический упорядоченный орграф, в котором:1) каждому истоку приписана некоторая переменная, причем разным истокам приписаны разные переменные (истоки при этом называются входами схемы, а приписанные им переменные — входными переменными);2) каждой вершине, в которую входят k ≥ 1 дуг, приписана функция из базиса Б, зависящая от k переменных (вершина с приписанной функцией при этом называется функциональным элементом);3) некоторые вершины выделены как выходы (истоки одновременно могут являтьсявыходами).Индукцией по глубине q вершины v определяется функция fv, реализуемая в даннойвершине.

Если q = 0, то есть v — исток, и v приписана переменная xi, то fv ≡ xi. Пусть реализуемые функции уже определены для всех вершин глубины меньшей, чем q0, и глубина vравна q0. Пусть в v входят дуги e1, e2, …, ek из вершин v1, v2, …, vk и в них реализуются функции f1, f2, …, fk. Пусть вершине v приписана функция g (x1, …, xk). Тогда в v реализуетсяфункция fv = g (f1, f2, …, fk).Определение 7.

Будем говорить, что схема реализует систему функций, реализуемых вее выходах.Определение 8. Сложностью схемы из функциональных элементов называется числофункциональных элементов в схеме.В дальнейшем по умолчанию будем подразумевать под базисом функциональных элементов систему Б0 = ∨,&, . Так как все эти функции симметричны относительно своих переменных, то дуги, входящие в каждую вершину, можно не упорядочивать.Пример. Полусумматор. Пусть v и v1 — выходы на рисунке, f v = xy & (x ∨ y ) = x ⊕ y ;f v1 = xy . Сложность (число элементов) полусумматора равна 4.{}xyxy &xy_v1v2v &∨Полусумматор Σ′23x∨yВ дальнейшем при построении схем ячейку полусумматора будем обозначать простоxyΣ′⊕&Ячейка полусумматора Σ′Пусть есть 2 n-разрядных числа, и требуется найти их сумму (в дальнейших обозначениях xi, yi — разряды чисел, а qi — единицы переноса).q0+z0q1x1y1z1q2x2y2z2!!!!qn−1xn−1yn−1z n−1xnynznПри i = 1, 2, …, n – 1 задача решается системой функцийzi = xi ⊕ yi ⊕ qi ,qi−1 = m(xi , yi , qi ) = xi yi ∨ yi qi ∨ qi xi .Таким образом, ячейку сумматора можно построить следующим образом:xyqΣ′·Σ′⊕·⊕v′′∨v′Ячейка сумматора Σ1где fv′′ = (x ⊕ y) ⊕ q, fv′ = xy ∨ (x ⊕ y) · q = xy ∨ (x ∨ y) · q = m (x, y, q).

Ячейку сумматора будемобозначать Σ1 и в дальнейшем в схемах подставлять вместо ячейки сумматора символ Σ1 стремя входами (x, y, z) и двумя выходами (z, q′).xyqΣ1q′zЯчейка сумматора Σ1Заметим, что сложность схемы, реализующей ячейку сумматора равна L (Σ1) = 9. Очевидно,zn = xn ⊕ yn, qn – 1 = xnyn, z0 = q0.24§23. Сумматор. Верхняя оценка сложности сумматора.

Вычитатель.Для набора α~ = (α1 ,α 2 ,! ,α n ) будем обозначать α~ = (α1α 2 !α n )2 .Определение 1. Сумматором Sn порядка n называется схема с 2n входами x1, x2, …, xn,y1, y2, …, yn и n + 1 выходом z0, z1, z2, …, zn такая, что ~z = S n (~x, ~y) = ~x+~y.Теорема 1. Существует схемный сумматор порядка n в базисе {∨, &, } с числом элементов 9n – 5.Доказательство. Построим искомый схемный сумматор. Для этого возьмём одну ячейку полусумматора, содержащую четыре элемента и n – 1 ячейку сумматора, каждая из которых содержит девять элементов.

Построим из этих частей сумматор.xn ynΣ′znxn – 1 yn – 1xn – 2 yn – 2Σ1x1Σ1zn – 1Σ1…zn – 2y1z1z0Сумматор SnВычислим сложность построенной схемы: L (Sn) = 9L (Σ1) + L (Σ′) = 9(n – 1) + 4 = 9n – 5. Теорема доказана.Определение 2. Вычитателем Wn порядка n называется схема с 2n входами x1, x2, …, xn,y1, y2, …, yn и n выходами z1, z2, …, zn такая, что при ~x ≥ ~y~z = W (~x, ~y) = ~x − ~y .Теорема 2. Существует схемный вычитатель порядка n в базисе {∨, &,элементов 11n – 5.Доказательство.

Заметим предварительно, чтоα~ = (α1α 2 !α n ) = 2n − 1 − α~ .Действительно,(α1α 2 !α n )2(α1α 2 !α n )2(1 1 ! 1 )2+.= 2 −1nТогда вычитатель реализуется схемойx1 … xn y1 … yn––Sn–…z0 z1–znВычитатель Wn25} с числом(())Wn (~x, ~y)= ~x−~y = 2 n − 1 − 2n − 1 − ~x +~yи его можно построить, используя 2n отрицаний и 1 сумматор порядка n. При этом L (Wn) == 2n + L (Sn) = 2n + (9n – 5) = 11n – 5. Так как ~x ≥ ~y , то 2n − 1 − ~x +~y ≤ 2n − 1 , и выход вычитателя определен.