- •Едеральное агентство по образованию
- •Оглавление
- •Раздел 1. Элементы теории множеств 8
- •Раздел 2. Элементы комбинаторики 20
- •Раздел 3. Алгебра логики 36
- •Раздел 4. Синтез управляющих систем 62
- •Раздел 5. Теория графов 77
- •Введение
- •Раздел 1 элементы теории множеств
- •1.1. Множества и операции над ними
- •1.2. Алгебра множеств
- •1.3. Разбиение множества на подмножества
- •1.4. Кортежи и декартово произведение множеств
- •1.5. Отображение множеств
- •1.6. Отношения
- •1.7. Свойства бинарных отношений
- •1.8. Алгебра подмножеств
- •1.9. Задания для самостоятельной работы
- •Раздел 2 элементы комбинаторики
- •2.1. Комбинаторика
- •2.2. Различные комбинаторные соотношения
- •2.3. Свойства биномиальных коэффициентов. Биномиальная теорема. Полиномиальная теорема
- •2.4. Принцип включения и исключения
- •2.5. Формула решета
- •2.6. Производящие функции
- •2.7. Производящие функции числа основных комбинаторных объектов
- •2.8. Задания для самостоятельной работы
- •Раздел 3 алгебра логики
- •3.1. Булевы функции
- •3.2. Формулы
- •3.3. Сопоставление формулам над множеством функций
- •3.4. Свойства элементарных функций
- •3.5. Разложение булевых функций
- •3.6. Совершенная д. Н. Ф., совершенная к. Н. Ф.
- •3.7. Полные системы
- •3.8. Примеры полных систем
- •3.9. Полиномы Жегалкина
- •3.10. Единственность представления булевых функций полиномами Жегалкина
- •3.11. Методы построения полиномов
- •I. Метод построения с помощью таблицы.
- •II. Метод неопределенных коэффициентов.
- •III. Метод суперпозиции.
- •3.12. Замыкание. Свойства операции замыкания. Замкнутые классы
- •3.13. Классы и их свойства
- •3.14. Линейные функции и их свойства
- •3.15. Принцип двойственности
- •3.16. Самодвойственные функции, их свойства
- •3.17. Лемма о несамодвойственной функции
- •3.18. Монотонные функции, их свойства
- •3.19. Лемма о немонотонной функции
- •3.20. Теорема о полноте в р2
- •3.21. Предполные классы
- •3.22. Возможность выделить из любой полной системы полную подсистему, состоящую из не более чем 4-х функций
- •3.23. Представление о результатах Поста
- •3.24. Задания для самостоятельной работы
- •Раздел 4 синтез управляющих систем
- •4.1. Схемы из функциональных элементов
- •4.2. Определение схем из функциональных элементов
- •4.3. Основные понятия и определения
- •4.4. Возможность реализации любой функции алгебры логики сфэ
- •4.5. Простейшие методы синтеза
- •4.6. Метод Шеннона
- •4.7. Асимптотически наилучший метод (метод о.Б. Лупанова)
- •4.8. Задания для самостоятельной работы
- •Раздел 5 теория графов
- •5.1. Элементы теории графов
- •5.2. Основные понятия и определения
- •5.3. Способы задания графа
- •5.4. Некоторые соотношения в графе
- •5.5. Перечисление графов
- •5.6. Оценка числа неизоморфных графов с p вершинами
- •5.7. Оценка числа неизоморфных графов с q ребрами
- •5.8. Укладки графов. Укладка графов в трехмерном пространстве
- •5.9. Планарность. Формула Эйлера для плоских графов
- •5.10. Следствия из формулы Эйлера для плоских графов
- •5.11. Операция подразделения ребра
- •5.12. Гомеоморфность графов
- •5.13. Теорема Понтрягина-Куратовского
- •5.14. Деревья и их свойства
- •5.15. Деревья и операции над ними
- •5.16. Оценка числа неизоморфных корневых деревьев на p вершинах
- •5.17. Задания для самостоятельной работы
- •Литература Основная
- •Дополнительная
- •Михеева Елизавета Алексеевна
5.8. Укладки графов. Укладка графов в трехмерном пространстве
Определение. Граф G обладает укладкой в некотором пространстве, если он изоморфен некоторому графу , изображенному в этом пространстве при помощи точек (представляющих вершины) и жардановых кривых (представляющих ребра), причем никакие 2 кривые нигде не пересекаются друг с другом, кроме инцидентной им обеим вершины.
Теорема 1. Каждый конечный граф может быть уложен в трехмерном пространстве.
Доказательство:
Пусть в графе G вершин. На прямой, перпендикулярной плоскостиS, расставляем все p вершин. Пусть множество ребер E состоит из ребер . Через прямую, на которой расставлены всеp вершин, проводим q плоскостей, перпендикулярных нашей плоскости S. Затем каждое ребро проводим на отдельной плоскости. Пересечений у этих ребер не будет, кроме вершин. В нашем доказательстве мы предъявили укладку в трехмерном пространстве. Теорема доказана.
5.9. Планарность. Формула Эйлера для плоских графов
Определение. Граф называется плоским, если он уложен на плоскости.
Определение. Граф называется планарным, если он изоморфен некоторому плоскому графу.
Пример: Пусть даны графы G и H, где G – плоский, H – не плоский, но планарный, так как .
Плоский граф разбивает нашу плоскость на области, которые называются гранями. Грани бывают ограниченными и неограниченными. В дальнейшем грани будем обозначать через , а число граней– через m.
Пример. Пусть дан граф:
где g1, g2 – ограниченные грани, g3 – неограниченная грань.
Теорема 2 (формула Эйлера). Пусть G – связный плоский граф, у которого p вершин, q ребер и m граней, тогда имеет место соотношение, что
p + m = q + 2. (2)
Доказательство (индукцией по q):
Пусть q=0, тогда граф имеет 1 вершину, т.е. p = 1, m = 1, так как грань только одна – неограниченная. Соотношение (2) справедливо, 1 + 1 = 0+ 2.
Пусть соотношение (2) справедливо для графа, число рёбер которого меньше q.
Теперь докажем справедливость соотношения (2) для графа с q рёбрами.
Рассмотрим произвольное ребро e графа G. Возможны 2 случая:
1) – петля. Тогда из графа G удалим это ребро e, получим граф, у которого p вершин, q–1 ребер, m–1 граней. Но поскольку по индукционному предположению верна формула Эйлера, то p+m–1 = q–1+2. Прибавив 1 слева и справа, получим нашу формулу: p+m = q+2.
2) , где . Удаляем ребро e, получаем граф H. Возможны 2 случая:
а)
Граф H – связный, значит, мы можем прийти из вершины в вершину по другому маршруту. У графа H p вершин, (q–1) ребер и (m–1) граней, т.е. число граней уменьшается, так как вершины и лежат в разных гранях, а после удаления ребра е грани сливаются. Мы получили случай, аналогичный первому.
б)
Граф H – несвязный, т.е. после удаления ребра е получаем 2 связные компоненты графа H1, H2: H1 = (p1,q1,m1), H2 = (p2,q2,m2). Для H1 и H2 справедлива формула Эйлера по индукционному предположению p1+m1 = q1+2, p2+m2 = q2+2, p1+p2 = p, q1+q2 = q–1, m1+m2 = m+1, так как вместо одной бесконечной грани стало 2. Сложим наши равенства:
p1+p2+m1+m2 = q1+q2 +4 p+m+1 = q–1+4p+m = q+2.
Теорема доказана.