Представление бинарных отношений графами. - раздел Математика, КУРС ЛЕКЦИЙ ПО ДИСКРЕТНОЙ МАТЕМАТИКЕ Понятие Графа Используется В Математике Для Наглядного Представления Бинарных...
Понятие графа используется в математике для наглядного представления бинарных отношений, заданных на конечных множествах.
Граф представляет собой конечный набор точек плоскости (вершины графа). Часть вершин может быть соединена отрезками со стрелками или без них (дуги и рёбра). Фигура, состоящая из вершин и дуг (отрезки со стрелками), называется ориентированным графом. Фигура, состоящая из вершин и рёбер (без направлений), называется неориентированным графом. Пусть, например, даны конечные множества , . Зададим на этих множествах бинарное отношение: .
Полученная фигура называется графом отношения . Любое бинарное отношение, заданное на конечных множествах, может быть представлено в виде некоторого графа. Верно и обратное: всякий граф представляет собой некоторое бинарное отношение на тех конечных множествах, на которых определён граф.
Т.к. бинарные отношения между элементами множеств и являются подмножествами , то можно говорить о включении одного бинарного отношения в другое, а также о пересечении и объединении бинарных отношений, или о дополнении к бинарному отношению. Дополнение бинарного отношения определяют следующим образом: . Другими словами пара тогда и только тогда, когда .
Если на множестве заданы произвольные бинарные отношения и , то можно рассматривать произведение бинарных отношений, а так же единичное, нулевое и обратное бинарные отношения.
Определение 7: Произведение определим следующим образом: элементы находятся в отношении тогда и только тогда, когда во множестве существует хотя бы один такой элемент , что и .
Произведение бинарных отношений обладает свойством ассоциативности, но не коммутативно.
Определение 8: Единичным бинарным отношением (или диагональю) называется бинарное отношение , такое, что тогда и только тогда, когда . Другими словами единичное бинарное отношение задается множеством всех пар, для всех .
Для любого бинарного отношения на множестве имеет место равенство: , т. е. коммутативность в этом случае выполняется.
Отметим, что пустое (нулевое) бинарное отношение играет роль нуля при умножении бинарных отношений. Для любого бинарного отношения имеет место свойство: .
Для любого бинарного отношения , обратное отношение определяется следующим образом: тогда и только тогда, когда . Очевидным является тот факт, что , а также .
Замечание: Понятие бинарного отношения допускает обобщения. Если на множестве задано одно или несколько - местных отношений, то такое множество называется моделью. Теория моделей – это один из разделов современной алгебры.
ВОСТОЧНОУКРАИНСКИЙ НАЦИОНАЛЬНЫЙ УНИВЕРСИТЕТ... имени ВЛАДИМИРА ДАЛЯ... Фесенко Т Н...
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ:
Представление бинарных отношений графами.
Что будем делать с полученным материалом:
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
И порядка. Фактор-множество.
В данном параграфе будут рассмотрены некоторые виды бинарных отношений. Рассмотрим непустое множество и зададим на нём бинар
Булевы алгебры.
Определение 1: Пусть - отношение порядка на множестве
Трансфинитная индукция.
Понятие мощности множества является обобщением понятия количества элементов конечного множества. А число элементов во множестве – это натуральное число. Но над натуральными числами
Задачи для самостоятельной работы.
1) Доказать, что два множества равны тогда и только тогда, когда их пересечение и объединение совпадают.
2) Обозначим через множес
Формулы алгебры логики. Тавтологии.
В алгебре выводятся формулы, которые остаются верными, какие бы числа не подставляли вместо букв, входящих в эти формулы. Подобным образом в алгебре высказываний конструируются форм
Доказательство.
Необходимость: Пусть формулы и равносильны. Тогда, по определению, для люб
Формальный язык логики высказываний.
Таблицы истинности в логике высказываний позволяют ответить на многие вопросы. Например, является ли данная формула тавтологией, противоречием или выполнимой формулой; влечёт ли она
Теорема Поста.
В предыдущем параграфе были рассмотрены некоторые классы булевых функций. В каждый класс попадают функции, обладающие определённым свойством. Для удобства введём следующие обозначен
Правила комбинаторики.
Начнем с основных принципов комбинаторики, т.е. с правил.
Существует два общих правила комбинаторики: правило сложения и правило умножения.
Правило слож
Свойства сочетаний.
Одной из наиболее распространённых комбинаторных формул является формула числа сочетаний. Для упрощения подсчётов и для доказательства некоторых утверждений удобно использовать след
Комбинаторика с повторениями.
Одна из особенностей комбинаторных задач заключается в том, что в ней исключительно большую роль играет точность формулировки. Обычно в задаче по комбинаторике необходимо определить
Упражнения для самостоятельной работы.
1. Сколько всегочетырёхзначных натуральныхчисел? Сколько всего четырёхзначных натуральныхчисел, в записи которых нет одинаковых цифр?
Хотите получать на электронную почту самые свежие новости?
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Новости и инфо для студентов