Глава 2. Теория графов

Содержание

• Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «кемеровский государственный университет»
• Кафедра автоматизации исследований
• И технической кибернетики
• Дискретная математика
• Содержание
• Глава 1. Теория множеств. Дискретная теория вероятности......5
• Глава 2. Теория графов.....................................................................53
• Глава 3. Дискретные структуры: конечные автоматы, коды...76
• Глава 4. Алгебра логических функций..........................................88
• Глава 5. Логика высказываний и логика предикатов..............109
• Глава 6. Схемы переключателей. Комбинационные схемы...................................................................................................123
• Глава 1. Теория множеств. Дискретная теория вероятности
• Множества и операции над ними
• Упражнения
• 1.2. Векторы и прямые произведения множеств. Проекция вектора на ось
• Упражнения
• 1.3. Комбинаторика Правило суммы
• Правило произведения
• Число размещений без повторений
• Число размещений с повторениями
• Число перестановок без повторений
• Число сочетаний без повторений
• Упражнения
• 1.4. Введение в дискретную теорию вероятностей
• Свойства элементарных событий:
• Соотношения между событиями:
• Свойства операций над событиями:
• Упражнения
• 1.5. Соответствия и функции
• Взаимно однозначные соответствия и мощность множеств
• Упражнения
• 1.6. Отношения
• Способы задания бинарных отношений
• Свойства бинарных отношений
• Отношение эквивалентности
• Отношение порядка
• Лексико-графический порядок.
• Упражнения
• 1.7. Операции и алгебры
• Свойства бинарных алгебраических операций
• 1.8. Гомоморфизм и изоморфизм алгебр
• Полугруппы, группы, решетки
• Упражнения
• Глава 2. Теория графов
• 2.1. Основные определения, способы задания, основные классы, изоморфизм графов
• Способы задания графа
• Степени вершин графа
• Части, суграфы и подграфы
• Операции над частями графа
• Графы и бинарные отношения
• Упражнения
• Среди пар графов, изображенных на рисунке, указать пары изоморфных графов и пары неизоморфных графов. Ответ обосновать.
• Маршруты, цепи и циклы. Расстояния, диаметры, центры. Обходы. Разделяющие множества и разрезы
• Упражнения
• Деревья, их свойства. Характеристические числа графов. Сети
• Упражнения
• Глава 3. Дискретные структуры: конечные автоматы, коды
• 3.1. Машина Тьюринга
• Упражнения
• Основы теории кодирования
• Упражнения
• Глава 4. Алгебра логических функций
• 4.1. Основные определения
• Упражнения
• 4.2. Эквивалентные преобразования
• Упражнения
• 4.3. Дизъюнктивные и конъюнктивные нормальные формы
• Упражнения
• 4.4. Дизъюнктивные нормальные формы и импликанты
• Упражнения
• 4.5. Минимизация днф. Тупикова днф
• Упражнения
• 4.6. Алгебра Жегалкина
• Упражнения
• 4.7. Двойственность в алгебре логики. Самодвойственные функции
• Принцип двойственности
• Упражнения
• 4.8. Функциональная полнота систем
• Упражнения
• Глава 5. Логика высказываний и логика предикатов
• 5.1. Логика высказываний
• Алгебра логики
• Исчисление высказываний
• Упражнения
• 5.2. Логика предикатов
• Упражнения
• Глава 6. Схемы переключателей. Комбинационные схемы
• Схемы переключателей
• Комбинационные схемы
• Упражнения
• Литература
• 650043, Кемерово, ул. Красная, 6.