- •Предисловие
- •Тема 1. Элементы теории множеств и комбинаторики
- •§1. Понятие множества. Операции над множествами
- •Примеры решения задач
- •Задачи для самостоятельного решения
- •§2. Отображение множеств
- •Примеры решения задач
- •Задачи для самостоятельного решения
- •§3. Мощность множества
- •Примеры решения задач
- •Задачи для самостоятельного решения
- •§4. Основы комбинаторики
- •Пример решения задач
- •Задачи для самостоятельного решения
- •§5. Отношение на множестве
- •Примеры решения задач
- •Задачи для самостоятельного решения
- •Тема 2. Теория графов
- •§1. Основные понятия теории графов: графы, ориентированные и неориентированные графы, пути, маршруты, циклы
- •Примеры решения задач
- •Задачи для самостоятельного решения
- •§2. Понятие связности, смежности и инцидентности
- •Примеры решения задач
- •Задачи для самостоятельного решения
- •§3. Задача о кратчайшем пути
- •Примеры решения задач
- •Задачи для самостоятельного решения
- •§4 Задача Эйлера. Плоские, планарные и не планарные графы. Формула Эйлера
- •Примеры решения задач
- •Задачи для самостоятельного решения
- •§5. Раскраска графа. Хроматическое число и характеристический индекс графа
- •Алгоритм решения задачи о раскраске вершин графа
- •Алгоритм решения задачи о раскраске ребер графа
- •Примеры решения задач
- •Задачи для самостоятельного решения
- •§ 6. Представление графов в памяти компьютера. Код Харари
- •Примеры решения задач
- •Задачи для самостоятельного решения
- •Примеры решения задач
- •Задачи для самостоятельного решения
- •§8. Обход дерева. Понятие списка. Деревья и списки
- •Примеры решения задач
- •Задачи для самостоятельного решения
- •Тема 3. Булевы функции
- •§1. Совершенная дизъюнктивная нормальная форма (сднф)
- •Примеры решения задач
- •Задачи для самостоятельного решения
- •§ 2. Совершенная конъюнктивная нормальная форма (скнф)
- •Примеры решения задач
- •Задачи для самостоятельного решения
- •§3. Многочлены Жегалкина
- •Примеры решения задач
- •Задачи для самостоятельного решения
- •§4. Булевы функции и их свойства
- •Примеры решения задач
- •Задачи для самостоятельного решения
- •§5. Функциональная полнота. Теорема Поста
- •Примеры решения задач
- •Задачи для самостоятельного решения
- •Список рекомендуемой литературы Основная
- •Дополнительная
Примеры решения задач
Задача 1. Для графа G перечислить все вершины и ребра, указать степени всех вершин. Какие из них являются висячими, а какие изолированными?
v3
x3 x2
v6 v4 v2 x4
x1
v1 x6 x5
v5
Решение. v1, v2, v3, v4, v5, v6, v7 – вершины графа G; ребра графа G – х1, х2, х3, х4, х5. Вершина v1 имеет степень 1, так как ей инцидентно только одно ребро х1. Вершина v2 имеет степень 4, так как ей инцидентны ребра х1, х2, х4, х5. Вершина v3 имеет степень 2, так как ей инцидентны два ребра х2 и х3 и т.д. Вершина v7 имеет степень 0, так как нет ребер ей инцидентных. Таким образом, вершины v1 и v6 являются висячими, так как их степень равна 1. Вершина v7 является изолированной, так как она имеет степень 0.
Задача 2. Для графа G построить матрицу смежности А(G).
v2 x6
x3 x1
v5 v3
v1 x2
x5 x4
v4
Решение. Так как у графа 5 вершин, то размер матрицы А(G) будет 5х5. Так как вершины v1и v2 связаны ребром х1, то а12=1, так как вершины v1 и v3 связаны ребром х2, то а13=1, и т.д. В результате получаем матрицу смежности А(G):
Заметим, что матрица смежности А(G) обладает свойством симметрии.
Задача 3. Пусть дан орграф D. Записать для графа D матрицу смежности А(D) и матрицу инцидентности В(D).
v2
x6 v5 x5 x1
v6 v3
x7 v1 x2
x3 x4
v4
Решение. Орграф D содержит 6 вершин и 7 дуг, поэтому размер матрицы А(D) будет 6х6, а матрица В(D) – 6х7. Так как орграф D не содержит дуги из v1 в v1 (петли), то а11=0. Так как орграф D не содержит дуги из v1 в v2, то а12=0. Так как из вершины v1 в вершину v3 существует дуга х2, то а13=1 и т.д.
В результате получаем матрицу инцидентности А(D):
Матрица смежности А(D) орграфа D не обладает свойством симметрии.
Составим матрицу инцидентности В(D) орграфа D. Элемент b11=-1, так как в вершине v1 заканчивается дуга х1;
элемент b12=1, так как в вершине v1 заканчивается дуга х2 и т.д. В результате получаем матрицу инцидентности В(D):
Задача 4. Пусть дан граф G. Определить количество путей длины 3 из вершины v2 в вершину v5.
x6 v5 v3
x78 v4 x4 x1
x7 x5 x3
v1
v2 x2
Решение. Составим матрицу смежности графа G. Так как вершин у графа G равно 5, то матрица смежности имеет размерность 5х5.
Так как необходимо определить пути длины 3, то матрицу смежности возведем в 3-ю степень.
Так как элемент а25=1, то из вершины v2 в вершину v5 существует один путь длины 3, а именно х2 х4 х6.
Задачи для самостоятельного решения
Задача 1. Для графа G перечислить все вершины, все ребра, указать степени каждой из вершин. Какие из них являются висячими, а какие изолированными?
v2 v3 x2
x78 v4 x3 x1
x5 x4
v1
v6 v5
Задача 2. Для графа G записать матрицу смежности А(G).
v2 v3 x1
x88
x3 x4
v6 x2
x78 v4 x5
v5 v1
x68
Задача 3. Дана матрица смежности А(G) графа G. Восстановить по ней граф.
Задача 4. Для орграфа Д записать матрицу смежности A(G) и матрицу инцидентности В(Д)
v2 v4 x4
x8 x7 x5 x3 x1
v5
x6 v3 v1 x2
Задача 4. По матрице инцидентности В(Д) восстановить орграф.
Задача 5. Дана матрица смежности орграфа Д. Восстановить по ней орграф и найти число путей длины 4 из 1 вершины в 3. Указать эти пути.
Задача 6. Дана матрица смежности графа G. Восстановить по ней граф и найти число путей длины 3 из 2 вершины в 4. Указать эти пути.