- •Предисловие
- •Тема 1. Элементы теории множеств и комбинаторики
- •§1. Понятие множества. Операции над множествами
- •Примеры решения задач
- •Задачи для самостоятельного решения
- •§2. Отображение множеств
- •Примеры решения задач
- •Задачи для самостоятельного решения
- •§3. Мощность множества
- •Примеры решения задач
- •Задачи для самостоятельного решения
- •§4. Основы комбинаторики
- •Пример решения задач
- •Задачи для самостоятельного решения
- •§5. Отношение на множестве
- •Примеры решения задач
- •Задачи для самостоятельного решения
- •Тема 2. Теория графов
- •§1. Основные понятия теории графов: графы, ориентированные и неориентированные графы, пути, маршруты, циклы
- •Примеры решения задач
- •Задачи для самостоятельного решения
- •§2. Понятие связности, смежности и инцидентности
- •Примеры решения задач
- •Задачи для самостоятельного решения
- •§3. Задача о кратчайшем пути
- •Примеры решения задач
- •Задачи для самостоятельного решения
- •§4 Задача Эйлера. Плоские, планарные и не планарные графы. Формула Эйлера
- •Примеры решения задач
- •Задачи для самостоятельного решения
- •§5. Раскраска графа. Хроматическое число и характеристический индекс графа
- •Алгоритм решения задачи о раскраске вершин графа
- •Алгоритм решения задачи о раскраске ребер графа
- •Примеры решения задач
- •Задачи для самостоятельного решения
- •§ 6. Представление графов в памяти компьютера. Код Харари
- •Примеры решения задач
- •Задачи для самостоятельного решения
- •Примеры решения задач
- •Задачи для самостоятельного решения
- •§8. Обход дерева. Понятие списка. Деревья и списки
- •Примеры решения задач
- •Задачи для самостоятельного решения
- •Тема 3. Булевы функции
- •§1. Совершенная дизъюнктивная нормальная форма (сднф)
- •Примеры решения задач
- •Задачи для самостоятельного решения
- •§ 2. Совершенная конъюнктивная нормальная форма (скнф)
- •Примеры решения задач
- •Задачи для самостоятельного решения
- •§3. Многочлены Жегалкина
- •Примеры решения задач
- •Задачи для самостоятельного решения
- •§4. Булевы функции и их свойства
- •Примеры решения задач
- •Задачи для самостоятельного решения
- •§5. Функциональная полнота. Теорема Поста
- •Примеры решения задач
- •Задачи для самостоятельного решения
- •Список рекомендуемой литературы Основная
- •Дополнительная
Задачи для самостоятельного решения
Задача 1. Найти маршрут минимальной длины от пункта 1 к пункту 1.
7 5 7 8
2 5
1 2 8
7 5 5 3 6 6 11
1 9
2 3 3 4 4 4
10
7 4 6 8
Задача 2. Найти маршрут минимальной длины из вершины А в вершину В.
1 2
В
4 3
А
5
Задача 3. Найти маршрут минимальной длины от пункта 1 к пункту 10.
2 5 10 3 9
4 3 2 2
1 1
3 1 6 9 3 2
4 4 1 5 6
8 4 7 1 2
Задача 4. Найти кратчайший путь из вершины v1 в вершину v13.
v10 v9
v11 v8 v4 v3
v13
v7 v1
v12 v2
v5 v6
§4 Задача Эйлера. Плоские, планарные и не планарные графы. Формула Эйлера
Теория графов берет свое начало в 1736г. с решения знаменитым математиком Эйлером задачи о кенигсбергских мостах. Жителей Кенигсберга заинтересовал вопрос, могут ли они, начав путь с одного участка суши, обойти все семь мостов Кенигсберга, посетив каждый из этих мостов однажды, и и вернуться в пункт старта, не переплыв реки.
Эйлер переформировал задачу, изобразив участки суши в виде вершин, а мосты сделала ребрами графа. Напомним, что цепь в графе называется Эйлерова, если она содержит все ребра ровно 1 раз.
В графе с более чем одной вершиной есть эйлеров цикл тогда и только тогда, когда этот цикл включает все вершины графа.
Задача Эйлера. Обладает ли данный граф эйлеровым циклом или цепью?
Теорема Эйлера 1. Связный граф обладает эйлеровым циклом тогда и только тогда, когда все его вершины имеют четную степень.
2. Связный граф обладает эйлеровой цепью тогда и только тогда, когда ровно две его вершины имеют нечетную степень.
Граф называется плоским, если он расположен на плоскости так, что его ребра не пересекаются, кроме как в вершинах.
Граф называется планарным, если его можно расположить на плоскости так, что ребра не будут пересекаться.
Гранью плоского графа называется часть плоскости, ограниченная ребрами и не содержащая в себе ни ребер, ни вершин.
Так как планарный граф можно превратить в плоский, то понятие грани имеет смысл и для него.
Пусть В – вершина графа, Г – грань, Р – ребро. Тогда справедлива следующая формула (формула Эйлера): Г+В-Р=2.
Примеры решения задач
Задача 1.
1
2
3
4 – бесконечная грань.
Проверим справедливость формулы на графе из примера 1. Так как В=4; Р=6, то граней должно быть Г=2+Р-В=2+6-4=4. Получили четыре грани, указанные на рис.
Задача 2. Определить наличие эйлерова цикла или эйлеровой цепи в графе:
v2
v1 v3
v4
v5
Решение. Определим степень каждой из вершин графа. degv1=4; degv2=2; degv3=4; degv5=4; degv4=2. Так как все степени вершин графа четные, то по теореме Эйлера граф обладает эйлеровым циклом и как следствие не обладает эйлеровой цепью.
Задача 3. Выяснить, является ли граф плоским?
Решение. Так как этот граф можно распутать, т.е. преобразовать к виду
то он является планарным.