- •Глава 16. Специальные циклы и метрика графов 345
- •Глава 17. Графовые инварианты 404
- •Введение
- •Цели и задачи преподавания дисциплины «дискретная математика»
- •Модуль 1. Основы Теории множеств (2 кредита)
- •Комплексная цель и задачи изучения модуля
- •Глава 1. Исчисление множеств
- •1.1. Понятие множества
- •1.2. Способы задания множеств
- •1.3. Подмножество
- •2. Пустое множество не имеет собственных и истинных подмножеств.
- •3. Одноэлементное множество имеет два подмножества - сaмo себя и , т.Е. Не имеет собственных подмножеств.
- •Множество – это многое, мыслимое как единое.
- •Глава 2. Операции над множествами
- •2.1. Объединение множеств
- •2.2. Пересечение множеств
- •2.3. Разность множеств
- •2.4. Дополнение множества
- •2.5. Тождества алгебры множеств
- •2.6. Доказательства тождеств с множествами
- •Глава 3. Упорядоченные множества
- •3.1. Кортеж (Упорядоченное множество)
- •3.2. Декартово произведение
- •3.3. Операция проектирования множеств
- •3.4. График
- •Декартово произведение множеств позволяет перейти к графическому представлению упорядоченных множеств.
- •Глава 4. Отношения
- •4.1. Основные понятия отношений
- •4.2. Основные свойства отношений
- •4.3. Операции над отношениями
- •4.4. Основные свойства специальных отношений
- •4.5. Разбиение множеств
- •4.6. Отношение порядка
- •Использование отношений позволяет строить модели взаимосвязей между любыми обьектами в природе.
- •5. Соответствия
- •5.1. Определение соответствия
- •5.2. Операции над соответствиями
- •5.3. Понятия образа и прообраза при соответствии
- •5.4. Доказательства тождеств с соответствиями
- •5.5. Основные свойства соответствий
- •5.6. Функция
- •Глава 6. Упорядоченные бесконечные множества
- •6.1. Основные сведения об упорядоченных бесконечных множествах
- •6.2. Проблема континуума
- •Глава 7. Основные понятия теории мультимножеств
- •7.1. Понятие мультимножества
- •7.2. Операции над мультимножествами
- •Возможность многократного вхождения элементов в мультимножество создает новое качество и позволяет расширить класс описываемых, анализируемых и синтезируемых математических объектов.
- •8. Нечеткие множества
- •8.1. Нечеткие высказывания
- •8.2. Операции над нечеткими множествами
- •8.3. Нечеткие отношения и соответствия
- •Тестовые задания к модулю 1
- •24. Множество называется графиком, если каждый его элемент ...
- •25. Соответствие может быть задано … способом.
- •Критерии оценки
- •Нечеткие и приближенные высказывания, множества, соответствия и отношения позволяют формально задавать расплывчатую информацию в виде, удобном для обработки на эвм.
- •Глоссарий к модулю 1
- •Глава 1.
- •Глава 2.
- •Глава 3.
- •Глава 4.
- •Глава 5.
- •Глава 6.
- •Глава 7.
- •Глава 8.
- •Галилей Модуль 2. Основы теории алгоритмов (1,5 кредита) Комплексная цель и задачи изучения модуля
- •Глава 9. Введение в теорию алгоритмов
- •9.1. Понятие алгоритма
- •9.2. Основные свойства алгоритмов
- •9.3. Классификация алгоритмов
- •Контрольные вопросы
- •Задания для самостоятельной работы
- •10.1. Преобразование слов в произвольных абстрактных алфавитах
- •10.2. Числовые функции
- •10.3. Построение алгоритмов по принципу «разделяй и властвуй»
- •10.4. Представление алгоритма в виде детерминированного устройства
- •10.5. Универсальные схемы алгоритмов
- •10.5. “Жадные” алгоритмы
- •10.6. Нечеткие (расплывчатые) алгоритмы
- •Контрольные вопросы
- •Задания для самостоятельной работы
- •11.1. Анализ алгоритмов
- •11.2. Сложность алгоритмов
- •Контрольные вопросы
- •Задания для самостоятельной работы
- •Тестовые задания к модулю 2
- •Критерии оценки
- •Модуль 3. Алгебра логики (1,5 кредита) Комплексная цель и задачи изучения модуля
- •Глава 12. Элементы алгебры логики
- •12.1. Логические функции
- •12.2. Основные логические тождества и законы
- •12.3. Булевы функции одной и двух переменных
- •Контрольные вопросы
- •Задания для самостоятельной работы
- •13.1. Дизъюнктивная и конъюнктивная нормальные формы
- •13.2. Способы перехода от нормальных к совершенным нормальным формам
- •2. Графический способ.
- •13.4. Функциональная полнота бф
- •13.3. Алгебра Жегалкина
- •Контрольные вопросы
- •Задания для самостоятельной работы
- •14.1. Реализация булевых функций
- •14.2. Минимизация булевых функций
- •14.3. Карты Карно
- •14.4. Метод Квайна - Мак-Класски
- •14.5. Переход от бф к простейшим комбинационным схемам
- •Контрольные вопросы
- •Задания для самостоятельной работы
- •Критерии оценки
- •Глоссарий к модулю 3
- •Модуль 4. Основы Теории графОв (2 кредита) Комплексная цель и задачи изучения модуля
- •Глава 15. Введение в теорию графов
- •15.1. Способы задания графов и виды графов
- •15.1.1. Способы задания графов
- •15.1.2. Виды графов
- •15.1.3. Нечеткие неориентированные графы
- •Примеры решения задач
- •Вопросы для самоконтроля
- •Задания для самостоятельной работы
- •15.2. Маршруты, цепи, циклы
- •Примеры решения задач
- •Вопросы для самоконтроля
- •Задания для самостоятельной работы
- •При моделировании систем модели и алгоритмы нахождения маршрутов, цепей, циклов, разрезов, связности графов позволяют строить эффективные алгоритмы преобразования графов.
- •15.3. Нахождение кратчайших маршрутов (цепей)
- •15.3.1. Алгоритм Форда
- •15.3.2. Алгоритм Дейкстры
- •Примеры решения задач
- •Вопросы для самоконтроля
- •Задания для самостоятельной работы
- •Алгоритмы Форда и Дейкстры являются эффективным способом определения кратчайшей по стоимости цепи между двумя вершинами графа.
- •Глава 16. Специальные циклы и метрика графов
- •16.1. Эйлеровы и гамильтоновы цепи и циклы
- •16.1.1. Связь между эйлеровыми и гамильтоновыми графами
- •Примеры решения задач
- •Вопросы для самоконтроля
- •Задания для самостоятельной работы
- •16.2. Алгоритмы построения гамильтонова цикла
- •16.2.1. Алгоритм Робертса ─ Флореса
- •16.2.2. Алгебраический метод
- •Примеры решения задач
- •Вопросы для самоконтроля
- •Задания для самостоятельной работы
- •16.3. Задача о коммивояжере и алгоритмы ее решения
- •16.3.1. Алгоритм Хелда и Карпа
- •16.3.2. Геометрический метод решения
- •Примеры решения задач
- •Вопросы для самоконтроля
- •Задания для самостоятельной работы
- •16.4. Расстояния на графах
- •Примеры решения задач
- •Вопросы для самоконтроля
- •Задания для самостоятельной работы
- •16.5. Деревья
- •Примеры решения задач
- •Вопросы для самоконтроля
- •Задания для самостоятельной работы
- •Глава 17. Графовые инварианты
- •17.1. Цикломатическое и хроматическое числа графа
- •Примеры решения задач
- •Вопросы для самоконтроля
- •Задания для самостоятельной работы
- •17.2. Числа внутренней и внешней устойчивости графа
- •Примеры решения задач
- •Вопросы для самоконтроля
- •Задания для самостоятельной работы
- •Числа внутренней и внешней устойчивости относятся к инвариантам графа. Они позволяют определить специальные группы вершин в графах.
- •17.3. Планарность графов
- •17.3.1. Плоские и планарные графы
- •17.3.2. Эвристики для определения планарности
- •17.3.3. Минимизация пересечений ребер графов
- •Вопросы для самоконтроля
- •Задания для самостоятельной работы
- •17.4. Ориентированные графы
- •17.4.1. Способы задания
- •17.4.2. Решение стандартных графовых задач с использованием орграфов
- •17.4.3. Выделение сильносвязных компонент
- •17.4.4. Нечеткие ориентированные графы
- •Примеры решения задач
- •Вопросы
- •Задания для самостоятельной работы
- •175 Гиперграфы
- •Примеры решения задач
- •Вопросы для самоконтроля
- •Задания для самостоятельной работы
- •Тестовые задания к модулю 4
- •Критерии оценки
- •Глоссарий к модулю 4 Глоссарий к главе 1
- •Глоссарий к главе 2
- •Глоссарий к главе 3
- •Библиографический комментарий
- •Литература
- •Заключение
- •Приложение 1
- •Учебное издание Гладков Леонид Анатольевич, Курейчик Владимир Викторович, Курейчик Виктор Михайлович
4.2. Основные свойства отношений
Отношение = <Ф, М> называется полным отношением, если Ф = М2, т.е. (x,yM)(x y). Другими словами, для любых элементов x, y, принадлежащих множеству М, истинно высказывание, что элементы x, y находятся в отношении .
Отношение = < Ф, М > называется пустым, если график Ф является пустым множеством. То есть = < , М >. Другими словами, имеется область задания отношения, на котором не задан график отношения.
Отношение = < Ф, М > называется отношением равенства, если Ф = М. В теоретико-множественном плане можно записать, (x,yM)(x y x = y). Например задано = < Ф, М >, М = { 1, 2, 3 }, Ф = {<1, 1>, <2, 2>, <3, 3>}. Данное отношение является отношением равенства.
Отношение = < Ф, М > называется отношением неравенства, если Ф = М2\М, т.е. (x,yM)(x y x y). Например задано = < Ф, М >, М = { 1, 2, 3 }, Ф = {< 1, 2 >, < 2, 3 >, < 3, 1 > }. Данное отношение является отношением неравенства. Отношения «5 > 3» и «3 < 10» также являются примерами отношения неравенства.
4.3. Операции над отношениями
На отношения переносятся основные операции над множествами, но они могут выполняться только на одной и той же области задания.
Объединением отношений 1 и 2 на множестве М называется отношение 3:
12 = 3, 1 = < Ф1, М >, 2 = < Ф2, М >.
3 = < Ф1Ф2, М >,
<a, b> Ф1 Ф2 <a, b> Ф1 <a, b> Ф2 & a, b M.
Например, пусть имеем два отношения: 1 = < Ф1, М >, 2 = < Ф2, М >,
М = { 2, 3, 4 }, Ф1 = { <2, 1>, <2, 2>, <2, 4> },
Ф2 = { < 2, 1 >, < 2, 3 >, < 4, 4 > }.
Тогда объединение этих отношений 3 = < Ф3, М >, Ф3 = Ф1 Ф2 = { <2,1>, <2,2>, <2,4>, <2,3>, <4,4> }.
Отметим, что для операции объединения над отношениями справедлива следующая запись:
x (12) y x 1 y x 2 y.
Пересечением отношений 1 и 2 на множестве М называется отношение 3, для которого:
12 = 3, 1 = < Ф1, М >, 2 = < Ф2, М >,
3 = < Ф1Ф2, М >,
<a, b> Ф1 Ф2 <a, b> Ф1 & <a, b> Ф2 & a, b M.
Например, пусть имеем два отношения: 1 = < Ф1, М >, 2 = < Ф2, М >, M = {1, 2}, 1 = <{<1, 1>, <1, 2>}, {1, 2}>, 2 = < {< 1, 2 >, < 2, 2 >}, { 1, 2 }>,
Тогда пересечение этих отношений 3 = <Ф3, М> = <{< 1, 2 >}, {1, 2}>.
Отметим, что для операции пересечения над отношениями справедлива следующая запись:
x (12) y x 1 y & x 2 y.
Операции объединения и пересечения также, как и для множеств применимы для любого числа отношений.
Отношение 3 называется разностью отношений 1 и 2, если
1 = <Ф1, М>, 2 = <Ф2, М>, 3 = 1\2 = <Ф1\Ф2, М>,
<a, b> Ф1 \ Ф2 <a, b> Ф1 & <a, b> Ф2 & a, b M.
Например, пусть имеем два отношения: 1 = <Ф1, М>, 2 = <Ф2, М>, M = {1, 2, 3}, Ф1 = {<1, 2>, <2, 2>, <3, 3>}, Ф2 = {<1, 1>, <2, 2>, <3, 3>}. Тогда Ф3 = Ф1\Ф2 = {<1, 2>}. Разность этих отношений 3 = <Ф3, М> = < {<1, 2>}, {1, 2, 3}>.
Отметим, что для операции разности над отношениями справедлива следующая запись:
x
(1\2)
y
x 1
y & x
y.
Над отношения выполняются также операции инверсии и композиции.
Если = < Ф, М >, то инверсия -1 = < Ф-1, М >.
Для того, чтобы найти инверсию отношения, необходимо проинвертировать элементы его графика на множестве М. Отметим, что для операции инверсии над отношениями справедлива следующая запись:
х -1 у у х.
Например, для отношения = <Ф, М>, М = {1, 2, 3}, Ф = {<1, 1>, <1, 2>, <1, 3>}, инверсия -1 = <Ф-1, М> и Ф-1 = {<1, 1>, <2, 1>, <3, 1>}.
Композицией двух отношений является новое отношение, у которого компонируют графики отношений.
1 = <Ф1, M>, 2 = <Ф2, M>.
1•2 = <Ф1•Ф2, М>
Например, 1 = <Ф1, M>, 2 = <Ф2, M>, М = {1, 2, 3}, Ф1 = {<1, 1>, <1, 2>, <1, 3>, <3, 3> }, Ф2 = {<1, 1>, <2, 3>, <3, 1>, <3, 2>}. Тогда композиция графиков этих отношений равна Ф1•Ф2={<1, 1>,<1, 3>,<1, 2>, <3, 2>, <3, 1>}.
Отметим, что все операции над отношениями могут выполняться только на одной и той же области задания, и в результате выполнения операций снова получается отношение с той же самой областью задания.
Введем операцию, меняющую область задания отношений.
Пусть = < Ф, М > и АМ, тогда сужением отношения на множестве А называется новое отношение
1 = < ФА2, А >
Например, = < Ф, М >, М = { 1, 2, 3 }, Ф = {< 1, 1 >, < 1, 2 >, <1, 3> }, A = {1, 2}. Тогда 1 = <{< 1, 1 >, < 1, 2 >}, {1, 2}>.
