Операции над графами

Содержание

• Множества. Основные понятия.
• Операции над множествами и их свойства.
• Декартово произведение. Разбиение множеств.
• Алгебра множеств
• Отношение. Бинарное отношение
• Алгебра бинарных отношений
• Отображение. Виды отображений
• Отношение порядка. Изоморфизм упорядоченных множеств.
• Алгебраические системы. Изоморфизм алгебраических систем.
• Функции алгебры логики.
• Формулы. Реализация функций формулами.
• Эквивалентность формул. Свойства элементарных булевых функций.
• Двойственные функции. Принцип двойственности
• Разложение булевых функций по переменным. Сднф.
• Полнота и замкнутость.
• Представление булевых функций в виде полинома Жегалкина. Теорема Жегалкина.
• Классы т0, т1.
• Класс s.
• Класс м.
• Класс l
• Теорема о функциональной полноте. Проверка системы функций на полноту.
• Задача минимизации булевых функций.
• Задача минимизации булевых функций в геометрической постановке.
• Сокращенные днф.
• Тупиковые днф и решение задачи минимизации.
• Графы. Основные понятия.
• Орграфы. Основные понятия.
• Маршруты. Цепи. Циклы. Связность.
• Операции над графами