- •Г.С. Розаренов, в.А. Шаруда дискретная математика Учебное пособие
- •Воронеж 2008
- •Воронеж 2008
- •Введение
- •1. Множества
- •1.1. Основные понятия
- •Упражнения
- •1.2. Операции над множествами
- •Упражнения
- •1.3. Диаграммы Венна
- •Упражнения
- •1.4. Доказательства
- •Упражнения
- •1.5. Векторы, прямые произведения, проекции векторов
- •Упражнения.
- •2. Алгебра логики
- •2.1. Функции алгебры логики
- •2.2. Формулы. Реализация функций формулами
- •2.3. Эквивалентность формул. Свойства элементарных функций. Принцип двойственности
- •2.4. Разложение булевых функций по переменным. Совершенная дизъюнктивная нормальная форма
- •2.5. Полнота и замкнутость
- •2.6. Проблема минимизации булевых функций
- •Упражнения.
- •2.7. Упрощение д.Н.Ф. Тупиковые (относительно упрощения) д.Н.Ф.
- •Упражнения.
- •3. Язык логики предикатов
- •3.1. Основные понятия логики предикатов
- •3.2. Истинные формулы и эквивалентные соотношения
- •Упражнения.
- •4. Теория графов
- •4.1.Основные понятия
- •Г раф изоморфен
- •4.2. Способы задания графов
- •Матрица инцидентности (ij)
- •4.3. Операции над частями графа
- •4.4. Маршруты, пути, цепи, циклы
- •4.5. Дерево и лес
- •4.6. Сети
- •Упражнения.
- •5. Введение в теорию алгоритмов
- •5.1. Предварительные обсуждения
- •5.2. Блок-схемы алгоритмов
- •5.3. Машины Тьюринга
- •5.4. Некоторые операции над машинами Тьюринга
- •5.5. Рекурсивные функции
- •6. Автоматы
- •6.1. Определение основных понятий
- •6.2. Изоморфизм и эквивалентность автоматов
- •6.3. Сети из автоматов
- •6.4. Синхронные сети
- •6.5. Программная реализация логических функций
- •Заключение
- •394026 Воронеж, Московский просп., 14
4.3. Операции над частями графа
Граф Н называется частью графа G, HG, если множества его вершин и ребер V(H) и E(H) содержатся соответственно в V(G) и E(G). Если V(G) = E(G), то часть H графа G называется суграфом.
Суграф Н является перекрывающим для н-графа G, если любая вершина графа G инцидентна хотя бы одному ребру из H.
Подграфом G(V) графа G(V) с множеством вершин V V называется часть, которой принадлежат все ребра с обоими концами из H.
Над частями графа G производятся следующие операции:
Дополнение к части H определяется множеством всех ребер G, не принадлежащих Н:
E(H)E( )=; E(H)E( )=E(G)
Сумма H1 Н2 частей H1 и Н2 графа G:
V(H1 Н2)=V(H1) V(H2); E(H1 Н2)= E(H1) E(Н2)
Произведение H1 Н2:
V(H1 Н2)=V(H1) V(H2); E(H1 Н2)= E(H1) E(Н2)
Две части Н1 и Н2 не пересекаются по вершинам, если V(H1) V(H2)= а следовательно, и нет общих ребер: E(H1) E(Н2)=
Части Н1 и Н2 не пересекаются по ребрам, если E(H1) E(Н2)=
Если Н1 и Н2 не пересекаются по вершинам, то сумма называется прямой.
4.4. Маршруты, пути, цепи, циклы
Пусть G - н-граф.
Маршрутом в G называется такая последовательность ребер M(е1, е2,…, еn) в которой два соседних ребра еi-1 и ei имеют общую вершину. В маршруте одно и то же ребро может встречаться несколько раз. Начало маршрута - вершина V0, инцидентная ребру e1 и не инцидентная ребру е2; конец маршрута Vn инцидентен en и не инцидентен en-1. Если е1, е2 (en-1, en) - кратные , требуется дополнительное указание, какую из двух инцидентных вершин считать началом (концом) маршрута.
Маршрут, в котором совпадают начало и конец V0=Vn называют циклическим. Маршрут, в котором все ребра разные называют цепью. Цепь, не пересекающая себя (без повторяющихся вершин), называется простой цепью.
Циклический маршрут называют циклом, если он является цепью и простым циклом, если это простая цепь.
Вершины называются связанными, если имеется маршрут М с началом и концом. Связанные маршрутом вершины связаны также и простой цепью.
Граф G называют связным, если все его вершины связаны между собой.
Теперь пусть G-орграф.
Последовательность ребер, в которой конец каждого предыдущего ребра еi-1 совпадает с началом следующего ei, называют путем. В пути одно и то же ребро может встречаться несколько раз.
Началом пути является начало e0, концом – конец en, т.е. вершины v0 и vn .
Путь называется ориентированной цепью (цепью), если каждое ребро встречается в нем не более одного раза и простой цепью, если любая вершина графа G инцидентна не более, чем двум его ребрам.
Контур – путь, в котором v0 = vn. Контур называется циклом, если он является цепью, и простым циклом, если это простая цепь. Если граф содержит циклы, то он содержит и простые циклы: граф без циклов называется ациклическим.
Вершина vG называется достижимой из вершины vG если имеется путь L(v,…,v) с началом v и концом v.
Орграф называется связным если он связан без учета ориентации дуг, и сильно связным, если из любой вершины v в любую вершину v существует путь. Число ребер пути называется его длиной.
Расстоянием (v’,v) между вершинами v и v н-графа G называется минимальная длина простой цепи с началом v и концом v.
Центром называется вершина н-графа, от которой максимальное расстояние до других вершин являлось бы минимальным. Максимальное расстояние от центра G до его вершин называется радиусом графа r(G).
Эйлеров цикл – цикл графа, содержащий все ребра графа.
Эйлеров граф – граф, имеющий эйлеров цикл (эйлеров цикл можно считать следом карандаша, вычерчивающего этот граф без отрыва от бумаги).
Имеет место теорема Эйлера: конечный неориентированный граф G – эйлеров тогда и только тогда, когда он связан и степени всех его вершин четны.
Эйлерова цепь – цепь, включающая все ребра данного конечного н-графа G, но имеющая различные начало v' и конец v. Чтобы в конечном н-графе G существовал эйлеров цикл, необходимы и достаточны его связанность и четность степеней всех вершин, кроме начальной v' и конечной v (они должны иметь нечетные степени). Чтобы в конечном орграфе существовал эйлеров цикл, необходима и достаточна его связность, а также равенство степеней вершин этого графа по входящим и выходящим ребрам, т.е. 1(V) = 2(V),
V G.
Гамильтонов цикл – простой цикл, проходящий через все вершины рассматриваемого графа. Гамильтонова цепь – простая цепь, проходящая через все вершины графа с началом и концом в разных точках.