Горбатов В.А. - Фундаментальные основы дискретной математики. Информационная математика - 2000, страница 5

Пример графа был использован при рассмотрении группы Галуа (рис. 1.6). Рассмотрим задание бинарного отношения с помощью матрицы смежности и фактормножества. При матричном задании используют двумерную таблицу — матрицу смежности, каждой строке (столбцу) которой взаимно однозначно сопоставляют элемент множества М. Тогда каждая клетка (ь, у) взаимно однозначно соответствует элементам множества Мт. Клетку ((, у), которая соответствует элементу, принадлежащему Т С Мт, каким либо образом помечают, например, зачерняют или помещают в нее единицу; остальные клетки оставляют незачерненными или в них записывают нули. 31.3.

Бинарные отиошеиол, способы их гадаиил и сеойстеа 23 Рассьютрнм предложенную фон Нейыаноы блок-схему ЭВМ, потовая состоит на ыножестаа устройств М=(а, Ь,с,а,е), где а — устройства ввода, Ь вЂ” арнфметычеспое устройство (процессор), с— устройство упрааления, б — аазоыннающее устройстзо, е — устройстао аывода. Рассмстрны информационный обмен между устрайстааьш пы н ту, кото.

рые находятся а стпошенпн Т, если на устройства аи поступает ннфорыацня з устройство пьу. Это отношение можно гадать з виде матрицы смежности следующим образом: Ь с е 1 1 1 О 1 1 1 О 1 1'1 О О 1 О Граф (, задаваемый рассмотренным отношением Т, изображен на рис. 1.7. Здесь (и в дальнейшем) вершины графа изобралшются в виде кружков (иногда в виде точек), дуги — ' в виде стрелок, исходящих из т; и входящих в ту, если (т;, ту) Е Т; при этом вершина т1 — начало дуги, а вершина т— а ее конец. Рассмотрим задание бинарного отношения с с помощью фактормножества.

Окрестностью единичного радиуса элемента т; б М называется множество элемен- е тон т Е Мтаких,что (т;, т;) Е Т,Т С М~. Часто вместо термина окрестность единичного радиуса используют термин сечение. Множество окрестностей единичного радиу- Рнс. 1.7 са, взятых для всех элементов множества М при задании в нем отношения Т С Мз, называется фактормножеством М(Т множества М по отношению Т. Фактормножество М/Т полностью определяет отношение Т. Зададпы фапторыножестао для рассыатрнааемого прпыера з анде двух строк, з первой на поторых поместим элементы множества М, зо второй под паждыы элементом аазцшем озрестность едцннчного радиуса этого алемента: а Ь с И е (Ь,с,а) (с,а,е) (а,Ь,б,е) (Ь,с,е) (с)] Тогда вторая стропа гадает фазторыножестао М зо Т.

Бннарное отношение, задаваемое графам 0 = (М, Т) (рнс. 1.7), можно задать нперечнсленнеыегодуг: М=(а, Ь, с, И, е), Тьч((о,Ь), (а,с), (а,б), (Ь,с), (Ь,е), (Ь,|4), (с,о)„(с,Ь), (с,й), (с,е), (д,с), (й,ь), (й,е), (е,с)). Рассмотрим наиболее важные свойства бинарных отношений. Отношение Т в множестве М называется рефлексивным, если для каждого элемента т Е М справедливо (т, т) Е Т. Свойство рефлексивности при задании отношения матрицей смежности Гл. 1. Основы мнагасаршных мнохсестав 24 81.3.

Бинарные отаношения, способы их гадания и свойстава 25 характеризуется тем, что все элементы, лежащие на главной диагонали, отмечены (равны 1 или зачернены); при задании отношения графом каждый элемент имеет петлю — дугу вида (т> тп) ы, щт (рис. 1.8, а). Отношение Т в множестве М называется симметричным, если из (т;, ту) б Т следует О3 (т;, тпу) б М, т; ~ тпу. ! Матрица смежности симмев в тричного отношения являет- ся симметричной относительно Рнс. 1.8 главной диагонали, а при за- дании отношения в виде графа следствием симметричности является наличие между всякой парой вершин, находящихся в отношении Т, двух противоположно направленных дуг (рис.

1.8, б). Отношение Т в множестве М называется транэитивным, если из (т;, т ) б Т и (тпу, ть) б Т следует (т;, ть) б Т, где т;, тп, ть б М; тп; ,-4 тп,, т; 84 тпь, т; ,-Е ть В графе, задающем транзитивное отношение Т, для всякой пары дуг таких, что конец первой совпадает с началом второй, существует третья дуга, имеющая общее начало с первой и общий конец со второй (рис. 1,8, в), — тпранэиптивно эамынающая дуга. Отношение Т', задаваемое частичным графом С' графа С (см.

рис. 1.7), после удаления дуг (а, Ь), (а, д), (6, е) и (д, е) становится симметричным. Частичнььн графом С' графа С = (Ъ", У) называется граф вида С' = (1', У'), 1т' С У, т. е. граф С', С' С С, получается путем удаления дуг из графа С. Дуга называется иниидентной вершине п, если эта вершина является началом или концом дуги. При удалении, вершин н инцидентных с ними дуг получаем подграфС'графа С: С' С О.

Если в подграфеО', С' С С, удалены некоторые дуги, то получаем частичный подераф сг", СЬ С 0' С С С, графа О. Отношение Т", задаваемое частичным подграфом Са графа С (см. рнс. 1.7), полученным после удаления всех дуг, кроме (а, 6), (а, д), (6, е) и (Ы, е) и вершины с (рис. 1.9, а), ие обладает ни свойством симметричности (а), ни рефлексивности (р), ни транзитивности (т1).

Оценим, к какому из этих свойств отношение Та наиболее близко. Блиэостпь ьь(Т", гт) отношения Та к свойству будем оценивать минимальным числом дуг, которые нужно удалить или добавить к графу, задающему это отношение, для того, чтобы граф задавал отношение Т, которое обладает свойством ст, ст = а, р, т1. Для рассматриваемого примера (рис. 1.9, б) Ь(Т", а) = 4, т1(Т", р) = 4, Гь(Т", т1) = 1. Используя эти свойства, определим бинарное отношение упорядоченности, имеющее большое теоретическое и практическое значение. Г' в Рис. 1.8 Бинарное отношение В в множестве М, обладающее свойствами: рефленсивности (Ча б М) ((а, а) б В); антисимметричности (ча, Ь б М) (((а, Ь) б В (Ь, а) б В) ++ а = Ь); транэитпивностпи (Ча, 6, с б М) (((а, Ь) б В (Ь, с) б В) -+ (а, с) б В); называется отношением упорядоченности и обозначается <.

Бинарное отношение в множестве М, обладающее свойствами антирефлекснвности, антисимметричности и транзнтивности, называется отпношением стпрогой упорядоченности и обозначается <. Отношение В в множестве М, обладающее свойствами рефлексивности и транзитивности, называется отношением пред- порядка. Рассмотрим отношение включения С . Это отношение рефлексивно: М; С М; (множество М; включает самое себя); если М; С С Му и М С М;, то М; = М. и, следовательно, оно аятисимметрнчйо;если М С М и М С $уь, то М С Мь,значит, отношение С транзитивно. Отношение включения С является отношением упорядоченности <. Множество М с заданным в нем отношением упорядоченности < называется упорядоченным этим отношением. Если любые два элемента т; и т упорядоченного множества каходятся в отношении упорядоченности тп; < тп или т < т;, Гл.

1. Основы многосорпьмых мноисесшв 26 ~ 1.3. Бинарные отношения, сиособы их эадвния и свойства 27 то это множество называется линейно упорядоченным (цепью); в противном случае множество называется частично уиорядочеииым. Пример частично упорядоченного множества приведен на рис. 1.10 (в качестве отношения < рассмотрено отношение включения множеств С). Часто частично упорядоченное множество изображают в виде графов Н = (Ъ; <), у которых удалены все петли и все транзитивно замыкающие дуги.

Граф Н = (К < ), задающий частично упорядоченное множество с удаленными петлями и транзитивно а) (а,я1 а] (в1 а, я1 Рис. 1.10 аамыкаюшими дугами, называется диаграммой Хассе Н. Диаграмма Хассе Н, задающая частично упорядоченное множество, которое показано на рис. 1.10, а, изображена на рис. 1,10, б. Диаграмма Хассе известна с конца Х1Х века, и в течение многих лет ее применяли в генеалогии для указания родства. Понятие непосредственного старшего легко задается в частично упорядоченном множестве следующим определением: т; ноирываеп1 т ', это означает, что т < т; и не найдется такого элемента т,, что т <тс<т;.

Рассмотрим подмножество М' упорядоченного множества М. Если найдется элемент т б М такой, что т; < т для любого элемента т; подмножества М', то элемент т называется махсораитоб подмножества М', Аналогично, если найдется элемент тд б М' такой, что тд < т; для любого элемента т; подмножества М', то элемент тд называется мииорантоб подмножества М'. На диаграмме Хассе Н (рис. 1.10, б) элемент (х) является минорантой подмножества Ну, х), (а, х), (у, х, а)), элемент (а, х) — мажорантой подмножества 1(х), (а), Зу. Если мажоранта т подмножества М принадлежит М т б Ф ьс/ б М' то она называется максимальным злемени1ом (т„ь„с~ этого 3 подмножества.

Аналогично, если мнноранта тд подмножества М' принадлежит М', тд б М', то она называется минимальным зяементом (т„„„) подмножества М'. В диаграмме Хассе Н (рис. 1.10 б) минимальным и максимальным элементами подмно- 3 / жества ((х), (у, х), (а, х), (у, х, а)) являются соответственно (х), (у, х, а). Для пары элементов линейно упорядоченного множества всегда существуют максимальный (равный одному из них) и минимальный (равный другому) элементы. Пару элементов линейно упорядоченного множества т;, т, для которых т; < т. или ту < тб называют сравнимыми.

Если множество мажорант (минорант) в свою очередь имеет максимальный (минимальный) элемент, то его называют верхней (кипеней) гранью подмножества М'. Верхнюю (ннжнюю) грань множества М' обозначают вор М' (афпг'М'). Верхняя (нижняя) грань подмножества М', принадлежащая М' называется наибольшим (наименьшим) элементом подмно- 1 жества М'. Теорема 1.1. Упорядоченное мноисество М содерхсит ие более одного наибольшего (наимсньшего) элемента.