- •Лекция 2
- •Лекция 3
- •Лекция 4
- •Лекция 5
- •Лекция 13
- •Лекция 14
- •Лекция 16
- •Основные понятия
- •Понятие множества. Способы задания множеств.
- •Понятие множества. Способы задания множеств.
- •Отношения между множествами.
- •3, Операции над множествами.
- •Алгебра множеств.
- •Теорема о количестве подмножеств конечного множества.
- •Формула включений и исключений.
- •Лекция 2
- •1.Понятие вектора. Прямое произведение множеств.
- •2.Теорема о количестве элементов прямого произведения.
- •Понятие вектора. Прямое произведение множеств.
- •Теорема о количестве элементов прямого произведения.
- •Лекция 3
- •2. Понятие высказывания.
- •3. Логические операции над высказываниями
- •4.Формулы алгебры логики.
- •Лекция 4
- •2. Важнейшие равносильности алгебры логики.
- •3.Равносильные преобразования формул.
- •Задачи для самостоятельного решения
- •Лекция 5
- •Дизъюнктивная нормальная форма.
- •Конъюнктивная нормальная форма.
- •Проблема разрешимости.
- •Лекция 6
- •Функции алгебры логики.
- •3. Представление произвольной функции алгебры логики в виде формулы алгебры логики.
- •4.Приложения алгебры логики в технике (релейно-контактные схемы).
- •Контрольные вопросы
- •Лекция 7
- •Совершенная дизъюнктивная нормальная форма.
- •Совершенная конъюнктивная нормальная форма.
- •Совершенная дизъюнктивная нормальная форма.
- •2.Совершенная конъюнктивная нормальная форма.
- •Лекция 8
- •2.Понятие минимальной днф. Метод минимизирующих карт.
- •3.Метод Квайна.
- •4.Метод Карно.
- •5.Постановка задачи минимизации в геометрической форме.
- •6.Сокращенная днф.
- •7.Тупиковая днф. Днф Квайна.
- •Лекция 9
- •Некоторые логические операции. Двоичное сложение.
- •Полином Жегалкина.
- •Некоторые логические операции. Двоичное сложение.
- •Полином Жегалкина.
- •Лекция 10
- •Полная система . Достаточное условие полноты.
- •Критерий полноты системы булевых функций.
- •Независимые системы. Базис замкнутого класса.
- •Полная система. Достаточное условие полноты.
- •Критерий полноты системы булевых функций.
- •3. Независимые системы. Базис замкнутого класса.
- •Лекция 11
- •Понятие предиката.
- •Логические операции над предикатами.
- •1. Понятие предиката
- •2. Логические операции над предикатами
- •Лекция 12
- •2. Формулы логики предикатов.
- •Значение формулы логики предикатов.
- •4. Равносильные формулы логики предикатов.
- •Лекция 13
- •Построение противоположных утверждений.
- •3. Прямая, обратная и противоположная теоремы.
- •4. Необходимые и достаточные условия.
- •5. Доказательство методом от противного.
- •Задачи для самостоятельного решения
- •Лекция 14
- •2. Использование метода математической индукции для нахождения сумм конечного числа слагаемых
- •3. Использование метода математической индукции для доказательства неравенств и делимости выражений, зависящих от n на некоторое число
- •4. Обобщение метода математической индукции
- •Контрольные вопросы
- •Лекция 15
- •Операции над бинарными отношениями.
- •3. Свойства бинарных отношений.
- •4. Специальные бинарные отношения.
- •Контрольные вопросы
- •Лекция 16
- •Функция
- •1. 4. Отображение
- •Обратная функция
- •2. Свойства отображений и функций
- •3.Операции над функциями. Свойства операций
- •Контрольные вопросы
- •Лекция 17
- •Основные понятия .
- •2. Смежность, инцидентность, степени вершин.
- •3. Способы задания графов
- •Маршруты в неориентированном графе
- •Операции над графами.
- •Связность. Компоненты связности
- •Контрольные вопросы
- •Лекция 18
- •2. Метрические характеристики неориентированного графа
- •Минимальные маршруты в нагруженных графах
- •Задачи на деревьях
- •Цикловой ранг графа. Цикломатическое число
- •Контрольные вопросы
- •Лекция 19
- •Эйлеровы цепи и циклы
- •Гамильтоновы циклы и цепи
- •Эйлеровы цепи и циклы
- •Гамильтоновы циклы и цепи.
- •Контрольные вопросы
- •Лекция 20
- •Двудольный граф. Условие существования двудольного графа
- •Паросочетания . Реберные покрытия
- •Двудольный граф. Условие существования двудольного графа
- •Паросочетания. Реберные покрытия
- •Контрольные вопросы
- •Лекция 21
- •Основные определения
- •Алгоритм плоской укладки графа
- •Контрольные вопросы
- •Лекция 22
- •Способы задания ориентированного графа
- •Путь в ориентированном графе
- •4. Связность. Компоненты связности в орграфе
- •Контрольные вопросы
- •Лекция 23
- •2. Минимальные пути в нагруженных орграфах
- •3. Порядковая функция орграфа без контуров
- •Контрольные вопросы
3. Порядковая функция орграфа без контуров
Рассмотрим орграф D(V, X) , не содержащий контуров, и определим множества
Граф D (V, X) не содержащий контуров – бесконтурный орграф.
Определим для него множества:
V 0 = {u Î V | D (u) = Æ};
V
(*)
V2 = {u Î V \ (V0 È V1) | D (u) Í V0V1};
…………………………………….
Vr = {u Î V \ È Vk | D (u) Í Vk},
Где D(v) – множество образов, r – наименьшее число, такое, что V \ È Vk = Æ (k = 0, 1,…, r).
V0, V1, …, Vr – уровни графа.
Уровни образуют разбиение множества вершин V, то есть
È Vk = V (k = 0,1,…,r).
Справедливо утверждение:
Пусть D(V, X) – орграф, r 0, V0, …, Vr – непустые множества, удовлетворяющие (*), такие, что È Vk = V (k = 0,1,…, r). Тогда D – орграф без контуров.
Функция q (u), определенная на множестве вершин V орграфа без контуров D(V, X) и ставящая в соответствие любой вершине v V номер уровня, которому она принадлежит, называется порядковой функцией орграфа D (V, X).
Пример:
Разбить граф D (V, X) на уровни и изобразить в уровневом представлении.
1) Найдём вершины, не имеющие образов и присвоим номер уровня 0:
V0 = {u V | D (u) = } = {u4, u6}. Порядковые функции для v4 и v6 равны
q (u4) = 0, q (u6) = 0.
2) Найдём вершины, образами которых являются u4 и u6:
V1 = {u V \ V0 | D(u) Í {u4, u6}} = {u1, u5}. q (u1) = 1, q (u5) = 1.
3) V2 = {u V \ V0 D (u) Í {u4, u6, u1, u5}} = {u3}, q (u3) = 2.
4) Тогда V3 = {u2}, q (u2) = 3.
Итак, получили множества V0, V1, V2 и V3 такие , что их взаимное пересечение пусто, а объединение есть множество вершин V графа . Следовательно граф - без контуров.
Рассмотрим алгоритм выделения уровней орграфа D(V, X) без контуров, использующий задание графа матрицей смежности. Этот алгоритм легко реализуется на ЭВМ:
Шаг 1. Составим матрицу смежности. Образуем под этой матрицей строку 0, в i – том месте которой укажем число единиц в i – той строке матрицы. Уровень V0 образуют вершины, которым в строке 0 соответствует 0. если V = V0, то задача решена и V0 – единственный уровень орграфа D. В противном случае переходим к шагу 2.
Шаг 2. Образуем под строкой 0 строку 1, ставя под каждым нулем строки символ , а на любом другом i – том месте – число единиц в i – ой строке матрицы, не учитывая единицы в столбцах над символами в строке 1. Уровень V1 образуют вершины, которым в строке 1 соответствует число 0. Полагаем j = 1.
Шаг 3. Пусть при некотором j 1уже построены строки 0 , 1,…, j , по которым получены множества V0, …, Vj . Если строка j состоит из нулей и символов , то задача решена и при r = j V0, …, Vr – уровни орграфа. В противном случае переходим к шагу 4.
Шаг 4. Образуем под строкой j строку j+1, ставя под каждым нулем и символом символ , а на любом другом i – том месте – число единиц в i – ой строке матрицы, не учитывая единицы в столбцах над символами в строке j+1. Уровень Vj+1 образуют вершины, которым в строке j+1 соответствует число 0. Присваиваем j : = j + 1 и переходим к шагу 3.
Решим предыдущую задачу с помощью матрицы смежности и описанного алгоритма.
Согласно полученным строкам lj:
V0 = {u4, u6},
V1 = {u1, u5},
V2 = {u3},
V3 = {u2}.
Следовательно, для данного графа количество уровней – четыре. Изобразим граф в уровневом представлении:
V3 V2 V1 V0
Наряду с нахождением уровней орграфа без контуров этот алгоритм позволяет проверить наличие контуров у произвольного графа. Справедливо утверждение:
Орграф D(V, X) содержит хотя бы один контур тогда и только тогда, когда в результате применения алгоритма к графу D появляется строка j без нулей.
Такой граф не представим в виде уровней.
Рассмотрим пример. Проверить наличие контуров в орграфе D(V, X), заданном матрицей смежности:
Применяя алгоритм, получим:
Поскольку в строке 3 нет нулей, то орграф содержит хотя бы один контур.