- •Введение
- •1. Элементы теории множеств
- •1.1. Основные понятия и определения теории множеств
- •1.2. Операции над множествами и их свойства. Диаграммы Эйлера-Венна
- •1.3. Мощность множества
- •1.4. Взаимно однозначное соответствие между множествами
- •1.5. Счетные и несчетные множества
- •Задачи и упражнения
- •2. Элементы теории отношений
- •2.1. Бинарные отношения. Свойства отношений
- •2.2. Отношение эквивалентности и разбиения
- •2.3. Отношения порядка. Диаграмма Хассе
- •Задачи и упражнения
- •3.Функции, отображения и операции
- •4. Элементы теории графов
- •4.1. Основные понятия и определения теории графов
- •4.2. Типы графов
- •4.3. Матричные представления графов
- •4.5. Операции над графами
- •4.6. Метрические характеристики графа. Расстояние в графах
- •Затем, изымая степень, соответствующую вершине , получим
- •4.8. Достижимость и связность
- •4.8.1. Основные определения
- •4.8.2. Матрицы достижимостей
- •4.8.3. Нахождение сильных компонент
- •Алгоритм нахождения сильных компонент графа можно описать следующей последовательностью шагов
- •Таким образом, сильные компоненты графа можно находить по следующему алгоритму.
- •4.8.4. Базы и антибазы
- •4.9. Независимые и доминирующие множества
- •4.9.1. Нахождение всех максимальных независимых множеств
- •Опишем алгоритм нахождения всех максимальных независимых множеств вершин графа.
- •4.10. Покрытия и раскраски
- •4.11. Деревья, остовы и кодеревья
- •4.11.1. Основные определения
- •4.11.2. Алгоритм построения остова неорграфа
- •4.11.4. Обходы графа по глубине и ширине
- •Доказательство.
- •4.11.5. Упорядоченные и бинарные деревья
- •4.12. Эйлеровы циклы. Гамильтонов контур
- •4.12.1. Метод Флёри построения эйлерова цикла
- •Матрица м данного графа имеет вид
- •4.12.3. Алгебраический метод выделения гамильтоновых путей и контуров
- •4.13. Плоские и планарные графы
- •4.13.1. Формула Эйлера
- •4.13.2. Критерии анализа планарности
- •4.13.3. Алгоритм укладки графа на плоскости
- •Задачи и упражнения
- •5. Комбинаторика
- •5.1. Перестановки
- •5.2. Перестановки с неограниченными повторениями
- •5.3. Размещения
- •5.4. Сочетания
- •5.5. Сочетания с повторениями
- •5.6. Производящие функции для сочетаний
- •5.7. Производящие функции для перестановок
- •5.8. Циклы перестановок
- •Общее число дубликатов
- •5.9. Принцип включений и исключений
- •Почему появился ?
- •Задачи и упражнения
- •6. Алгебра высказываний
- •6.1. Операции над высказываниями
- •6.2. Правила записи сложных формул
- •6.3. Таблицы истинности
- •6.4. Равносильность формул
- •6.5. Дизъюнктивные и конъюнктивные нормальные формы
- •6.5.1. Алгоритм приведения пф к нормальным формам
- •6.5.2. Аналитический способ приведения к сднф
- •6.5.3. Табличный способ приведения к сднф
- •6.5.4. Табличный способ приведения к скнф
- •6.6. Логическое следствие
- •Задачи и упражнения
- •7. Разрешимые и неразрешимые проблемы
- •Заключение
- •Библиографический список
- •394026 Воронеж, Московский просп., 14
Задачи и упражнения
1. Доказать, что в неорграфе число вершин с нечетной степенью четно.
2. Построить граф (если он существует) с последовательностью степеней
а) (4,3,3,2,2);
б) (5,4,2,2,1) .
3. Привести примеры сильно связного, связного, несвязного графов.
4. Среди графов, изображенных на рис.4.57, указать сильно связный, односторонне связный и несвязный графы.
Рис. 4.57
5. Найти матрицы достижимости и контрдостижимости для графов G1 ,G2, G4, изображенных на рис. 4.57.
6. Доказать, что если в n-вершинном графе степень каждой вершины не меньше, чем (n-1)/2 , то он связен.
7. Доказать, что если G несвязный граф, то G связный.
8. Доказать, что в любом графе каждая его база содержит все вершины, имеющие нулевые полустепени захода.
9. Для графов, изображенных на рис. 4.58, найти сильнее компоненты, построить конденсацию, найти базы и антибазы.
Рис. 4.58
10. Доказать, что хроматическое число каждого n-вершинного дерева (n2) равно 2.
11. Что можно сказать о хроматическом числе объединения двух графов?
12. Граф называется критическим, если удаление любой из его вершин вместе с инцидентными ей ребрами приводит к графу с меньшим хроматическим числом. Показать, что Кn является критическим для любого n>1.
13. Показать, что всякий k-xpoмагический граф (k>l) содержит в качестве подграфа критический k-хроматический граф, и найдите такой подграф для графа на рис. 4.59.
Р ис.4.59
14. Определить раскраску графов, изображенных на рис. 4.60.
Рис. 4.60
15. Построить остовы для графов, изображенных на рис. 4.61.
Рис. 4.61
16. Доказать, что граф G является связным тогда и только тогда, когда он имеет остов.
17. Существует ли эйлеров цикл в графах, изображенных на рис. 4.62 ?
Рис. 4.62
18. Определить, какие из графов пяти правильных многогранников имеют эйлеровы циклы.
19. Составить алгоритм, основанный на алгоритме Флери и позволяющий найти все эйлеровы циклы графа.
20. Определить гамильтоновы пути и контуры методом перебора Робертса и Флореса в графах, изображенных на рис. 4.63.
Рис. 4.63
21. Для графа построить, если это возможно, его укладку на плоскости.
а) б)
в) г)
д )
е)
5. Комбинаторика
Комбинаторика – раздел математики о выборе и расположении элементов некоторого множества на основании каких-либо условий.
Комбинаторика стала выделяться в отдельный раздел математики в работах Б. Паскаля и Л. Ферма, хотя отдельные понятия и факты комбинаторики были известны ещё математикам античности и средневековья. Большой вклад в развитие комбинаторики внесли Г. Лейбниц, Я. Бернулли, Л. Эйлер. В их работах были даны определения основных понятий комбинаторики, развиты первые комбинаторные методы и указаны их применения, а также прослежена связь комбинаторики с исчислением вероятностей. Именно комбинаторика послужила фундаментальной основой началам теории вероятностей. При решении комбинаторных задач часто применяются два важных правила: умножения и сложения.
Правило умножения. Пусть требуется выполнить одно за другим какие-то k действий. Если первое действие можно выполнить n1 способами, второе действие - n2 способами, третье - n3 и так до k – го действия, которое можно выполнить nk способами, то все k действий вместе могут быть выполнены n1n2 n3 nk способами.
Правило сложения. Если два действия взаимно исключают друг друга, причем одно из них можно выполнить m способами, а другое – n способами, то выполнить одно любое из этих действий можно n + m способами.