- •Учебно-методический комплекс дисциплины сд.12 дискретная математика
- •061800 «Математические методы в экономике»
- •Раздел 1. Программа учебной дисциплины. Структура программы учебной дисциплины
- •1.3 Пояснительная записка:
- •1.5. Объем дисциплины и виды учебной работы.
- •1.6 Содержание дисциплины.
- •1.7 Методические рекомендации по организации изучения дисциплины.
- •1.8 Учебно-методическое обеспечение дисциплины.
- •1.9 Материально-техническое обеспечение дисциплины.
- •1.10 Примерные зачетные тестовые задания.
- •1.11 Примерный перечень вопросов к зачету (экзамену).
- •1.12 Комплект экзаменационных билетов
- •1.13 Примерная тематика рефератов.
- •1.14 Примерная тематика курсовых работ.
- •Элементы теории множеств
- •§ 2. Бинарные операции и их свойства
- •§ 3. Операции над множествами. Законы де Моргана
- •§ 4. Вектор. Прямое произведение
- •§ 5. Мощность конечного множества
- •§ 6. Отношения и их свойства
- •§ 7. Отношение эквивалентности
- •§ 8. Отношение порядка
- •§ 9. Отображения и их свойства
- •Глава II. Элементы теории графов
- •§ 1. Графы, их вершины, рёбра и дуги
- •§ 2. Операции над графами
- •§ 3. Способы задания псевдографов. Степени вершин
- •§ 4. Отношение связности для вершин неориентированного графа
- •§ 5. Отношение достижимости для вершин орграфа
- •§ 6. Эйлеров граф и условия его существования
- •§ 7. Гамильтонов граф и условия его существования
- •§ 8. Деревья и их свойства. Цикломатическое число
- •§ 9. Формула Кэли
- •§ 10. Двудольный граф
- •§ 11. Планарность
- •§ 12. Раскраска графов
- •Глава III. Булевы функции
- •§ 1. Основные определения
- •§ 2. Свойства булевых функций
- •§ 3. Переключательные функции
- •§ 4. Совершенные нормальные формы
- •§ 5. Полнота. Примеры полных систем
- •§ 6. Замыкание и его свойства
- •§ 7. Важнейшие замкнутые классы
- •§ 8. Теорема о функциональной полноте
- •Раздел 4. Словарь терминов (глоссарий) Элементы теории множеств
- •Конечные графы
- •Функциональные системы с операциями: алгебра логики
- •Раздел 5. Практикум по решению задач (практических ситуаций) по темам лекций (одна из составляющих частей итоговой государственной аттестации) Элементы теории множеств
- •Задачи для самостоятельного решения
- •Конечные графы
- •Задачи для самостоятельного решения
- •Функциональные системы с операциями: алгебра логики
- •Задачи для самостоятельного решения
- •Раздел 6. Изменения в рабочей программе, которые произошли после утверждения программы.
- •Раздел 7. Учебные занятия по дисциплине ведут:
§ 5. Отношение достижимости для вершин орграфа
Пусть V - множество вершин ориентированного графа F, Е - множество его рёбер. Каждое ребро eE имеет начало v’V и конец v’’V. Таким образом, заданы два отображения 1 и 2, где v’=1(e) начало ребра е, v’’ =2(e) конец ребра е.
Можно дать несколько определений пути в орграфе F.
1. Путь из вершин и рёбер это последовательность L(v0,e1,v1,e2,...,en,vn ), где vi1=1(ei), vi=2(ei). Вершина v0 называется началом пути L, вершина vn - концом пути L, число n рёбер его длиной. Путь, состоящий из одной вершины, имеет нулевую длину.
2. Путь из рёбер это последовательность(e1,e2,...,en ). Это понятие пути аналог понятия маршрута в неориентированном графе.
3. Путь из вершин это последовательность(v0,v1,...,vn ). Путь из вершин определён для графов, не содержащих кратных рёбер.
На практике можно пользоваться тем определением пути, которое окажется удобнее в данной конкретной задаче.
Путь называется ориентированной цепью (или просто цепью, когда рассматриваются только орграфы),, если каждое ребро встречается в нём не более 1 раза, и простой ориентированной цепью, если каждая вершина графа F инцидентна не более чем двум его рёбрам.
Пример. Путь (e5,e6,e7,e1,e4,e3) (рис. 3.11) ор. цепь, а путь (e7,e1,e4,e3) - простая ор. цепь.
Рис.
3.11.
Пример. Путь (e1,e4,e3,e2,e5,e6,e7) цикл, путь (e5,e6,e7) простой цикл.
В связи с ориентированными цепями справедлива теорема, которую доказал Redei при изучении квадратичных полей.
Теорема 3.3. Пусть F конечный орграф, в котором каждая пара вершин соединена ребром. Тогда в F существует простая ориентированная цепь, проходящая через все его вершины.
Доказательство проведем методом МИ. Обозначим количество вершин графа через n.
-
n=2: дуга, соединяющая две вершины графа F2, и есть простая ориентированная цепь, проходящая через все вершины графа.
-
Предположим, что при n = m для графа Fm теорема верна.
-
Докажем, что при n = m+1 для графа Fm+1 теорема верна.
Построим граф Fm+1, добавив к графу Fm некоторую вершину vm+1, в которой имеются ребра ко всем вершинам vi (i=1,2,...,m) из Fm. По предположению, существует простая ориентированная цепь, проходящая через все вершины графа Fm: Pm=(v1,v2,...,vm). Для ребер, инцидентных вершине vm+1, имеется три возможности.
1. Существует дуга (vm+1,v1). Добавив ее к цепи Pm “слева”, получим искомую цепь, проходящую через все вершины графа Fm+1: Pm+1=( vm+1,v1,v2,...,vm).
2. Существует дуга (vm,vm+1). Добавив ее к цепи Pm “справа”, получим искомую цепь, проходящую через все вершины графа Fm+1: Pm+1=( vm+1,v1,v2,..., vm,vm+1).
3. Если в графе Fm+1 нет ни дуги (vm+1,v1), ни дуги (vm,vm+1), то при некотором k (k=2,3,...,m-1) в нем обязательно найдутся дуги (vk ,vm+1) и (vm+1,vk +1). Составим цепь
Pm+1=(v1,v2,...,vk ,vm+1,vk +1,...,vm).
Эта цепь проходит через все вершины графа Fm+1.
На множестве вершин V зададим отношение достижимости RD следующим образом: Вершина v’V находится в отношении RD с вершиной v’’V (в этом случае говорят, что вершина v’’ достижима из вершины v’), если существует путь L(v’,... ,v’’) с началом v’ и концом v’’.
Аналогично отношению связности для вершин неориентированного графа отношение достижимости для вершин ориентированного графа рефлексивно и транзитивно, но в отличие от отношения связанности отношение достижимости не обязательно симметрично.
С помощью отношения достижимости определяется разбиение множества вершин орграфа на классы эквивалентности: вершины v’, v’’ принадлежат одному классу, если отношение симметрично, т.е. v’’ достижима из v’, а v’ достижима из v’’.
Пусть L1(v’, ... ,v’’) и L2(v’’, ... ,v’) соответствующие пути, связывающие эти вершины. Тогда вместе они образуют цикл, проходящий через вершины v’ и v’’. Таким образом, любые вершины одного и того же класса эквивалентности принадлежат некоторому циклу. Если циклы в графе отсутствуют, то каждый класс эквивалентности состоит из одной вершины.
Рис.
3.13.
Если существует базисный граф, то он не обязательно единственный. Так, для графа на рис. 3.13, любое радиальное ребро и ориентированный многоугольный цикл определяют базисный граф.
Если F - конечный орграф, то базисные графы существуют; они могут быть получены при последовательном удалении “излишних” рёбер (v0,vn), для которых найдётся не содержащая ребра (v0,vn) ориентированная цепь Р(v0,vn).