- •Учебно-методический комплекс дисциплины сд.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. Учебные занятия по дисциплине ведут:
Глава II. Элементы теории графов
§ 1. Графы, их вершины, рёбра и дуги
Рассмотрим множество V={v1,v2,...,vn}, n2, и множество E={e1,e2,...,em}, элементами ek которого являются двухэлементные подмножества {vi, vj} множества V. Пара множеств V и E называется неориентированным графом F(V,E) с множеством вершин V и множеством ребер E. При этом говорят, что неориентированное ребро ek соединяет вершины vi, vj или ребро ek и вершины vi, vj инцидентны. Вершины vi и vj называют смежными.
Граф F(V,E) может быть изображен геометрически. Для этого некоторые n точек трехмерного пространства помечаются элементами множества вершин V и вершины vi и vj соединяются линией, если {vi, vj} Е. Геометрическое изображение графа будем называть диаграммой.
Пример 3.1. Пусть V={v1,v2,v3,v4}, а элементами множества E являются все возможные множества вида {vi, vj} при i,j=1,2,3,4; ij. Диаграмма графа приведена на рис. 3.1, а.
Пусть теперь множество E={e1,e2,...,em} представляет собой некоторое бинарное отношение на множестве V (EVV). Тогда пара множеств V и E называется ориентированным графом (орграфом) F(V,E) с множеством вершин V и множеством ребер E.
Ребро ориентированного графа называется дугой. Для дуги ek=(vi, vj) вершина vi называется начальной, а vj конечной. Иными словами, ребро ek выходит из вершины vi и заходит в вершину vj. Как и в случае неориентированного ребра, дуга ek инцидентна вершинам vi и vj, а вершины vi и vj инцидентны дуге ek. Вершины vi и vj также называют смежными.
Ребро, у которого концевые точки совпадают, называется петлей.
Пример 3.2. Пусть V={3, 8, 24}. Зададим на этом множестве отношение
E={(u,w)/ u - делитель w; u,wV}={(3,3), (3,24), (8,8), (8,24), (24,24)}.
Рис.
3.1.
Из приведенных определений графов следует, что в них отсутствуют кратные, или параллельные, ребра, соединяющие одни и те же пары вершин. Кроме того, в неориентированном графе не допускаются петли. Однако иногда удобно снять указанные ограничения.
Граф, содержащий кратные ребра называется мультиграфом. Граф, содержащий петли и (или) кратные ребра, называется псевдографом.
Два графа F и F* изоморфны, если существует такое взаимно однозначное соответствие между множествами их вершин V и V*, что вершины соединены рёбрами в одном из графов тогда и только тогда, когда соответствующие им вершины соединены в другом графе. Если рёбра ориентированы, то их направления также должны соответствовать друг другу. Все изоморфные графы имеют одинаковые свойства.
Вершина, не инцидентная никакому ребру, называется изолированной. Граф, состоящий только из изолированных вершин, называется нуль-графом (пустым графом) и обозначается через 0. Для нуль-графа множество ребер пустое: Е=.
Другим важным частным случаем является полный граф, в котором каждая вершина множества V соединена ребром со всеми остальными вершинами этого множества. В дельнейшем полный неориентированный граф с n вершинами будем обозначать Kn. В ориентированном полном графе для каждой пары вершин имеются два ребра: по одному в каждом направлении.
Пример. На рис. 3.1, а представлен граф K4.
Граф H(VH, EH) называется частью графа F(V, E) (обозначение: HF), если VH V, EH E. Нуль-граф является частью каждого графа.
Рис.
3.3.
Если V* = V, то подграф F*(V*, E*) совпадает с F(V, E). В противном случае подграф F*(V*, E*) называется собственным подграфом графа F*(V*, E*). Для единичной вершины V* = {а} подграф F*(V*, E*) состоит из петель в а.
Пример (рис. 3.3). Для графа 3.3, а граф 3.3, б является частью, но не является подграфом, тогда как граф 3.3, в является для графа 3.3, а как частью, так и подграфом.
Число неориентированных графов с n вершинами
Пусть имеется n вершин, помеченных соответственно: v1, v2,..., vn. Подсчитаем количество различных диаграмм, которые можно построить на этих вершинах. Максимальное количество ребер в графе определяется количеством способов, которыми из n вершин можно выбрать две: =Сn2. Для каждого ребра существует две возможности: либо его проводят, либо нет. В соответствии с правилом произведения в комбинаторике, количество диаграмм, а значит, и графов, равно 2.
Число неориентированных графов с n вершинами и m ребрами
Пусть по-прежнему имеется n вершин, помеченных соответственно: v1, v2,..., vn. Графов с m ребрами столько, сколько существует способов из всех =Сn2 ребер выбрать m ребер, т.е Сm.