Бинарные отношения и графы

ЛЕКЦИЯ_ДМ № 5 БИНАРНЫЕ ОТНОШЕНИЯ и ГРАФЫ Отношения на множестве Соответствия S, определённые на двух тождественных множествах A и B или, что тоже, на одном и том же множестве, называются отношениями, которые обозначим R. Исходя из понятия S  A  B , определим R, как R  A  A  A2 – подмножество множества конечной декартовой степени n: An, т.е. множество векторов ( а1 ,.., аn ), состоящих из n элементов множества A, которое является соответствием, отображением на подмножестве R множества A. n Тогда, множество R  A называется n–местным (n–арным) отношением на множестве A (называемом носитель). Двухместные отношения называются бинарными, трёхместные – тернарными. Аналогия из математического анализа: упорядоченные пары, тройки и т.д., эти элементы ( а1 ,.., аn )R, являющиеся точками n-мерного пространства An, принадлежит многомерному множеству R, называемому отношением. Говорят, что элементы а1 ,.., аn находятся в отношении R если ( а1 ,.., аn )R. Запись R а1 ,.., аn  означает, что а1 ,.., аn  R. В бинарном случае пользуются обозначениями:  а, b   R или R  а, b   aRb . Одноместные (унарные) отношения aR и RA определяют свойства (признаки) элементов и множеств. Примером бинарного отношения является множество супружеских пар, тернарного отношения может служить множество троек нападающих в хоккейной команде. Каждый из нападающих находится в отношении со всеми игроками своей тройки, не исключая участия в других тройках. Особенно часто употребляются бинарные отношения на множестве вещественных чисел. Любую функцию (n-1) переменной можно рассматривать как n-арное отношение. Например, функция двух переменных y  F ( x1 , x2 )  x1  x2 есть тернарное отношение F  X 1  X 2  Y , элементами которого являются тройки чисел: (1,2,2), (2,4,8) и т.д. Отношение равенства (подобия) на множестве A:    a, a,..., a   a  A n называется диагональю множества A (по аналогии с диагональю матрицы). Наиболее часто встречающиеся и хорошо изученными являются бинарные отношения: R  A  A  A2 . Если a  A и b  A находятся в отношении R, это часто записывается как аRb. Любую функцию одной переменной, определённую на множестве вещественных чисел можно рассматривать как бинарное отношение f. Так, например, для функции y  f ( x)  x 2 справедливо 1f1, 2f4, 3f9 и т.д. 1 В дальнейшем слово «бинарные» будем обычно опускать, когда речь будет идти только о бинарных отношениях. Отношения могут определяться различными способами. Например, отношения порядка на числовых множествах (5 видов): «меньше» (<), «меньше или равно» (  ), «больше» (>), «больше или равно» (  ), «равно» (=). Примеры 2.1. Пусть R есть отношение «>» на множестве 1,2,3 ,т.е. R  1,2,3 1,2,3 Тогда в состав R входят пары: (2,1), (3,1), (3,2). Если R есть отношение «=», то (1,1)  R или 1R1; (2,2)  R или 2R2; (3,3)  R или 3R3. Примеры 2.2. Отношения для пар целых чисел, меньших 10. а) Отношение “  ” выполняется для пар: (0,8) и (9,9), но не выполняется для пары (9,7). б) Отношение «иметь общий делитель  1» выполняется для пар: (6,9), (4,2), (2,4), (4,4), но не выполняется для (5,7) и (9,7). в) Отношение «быть делителем» (aRb – означает: а – делитель b) выполняется для пар (2,4) и (4,4), но не выполняется для (4,2) и (7,9) Примеры 2.3. отношения на множестве точек действительной плоскости: 1) отношение «находится на одинаковом расстоянии от начала координат» совпадает с отношением «находиться на одной и той же окружности с центром в начале координат». (подобрать пары) 2) «Симметричность относительно оси Ох» выполняется для тех пар точек (х, у,) и х2 , у2  , для которых х1  х2 и у1   у2 . Пример 2.4. отношения на множестве людей: «жить в одном городе», «быть моложе», «быть сыном», «быть знакомым». Отношения на конечных множествах обычно задаются списком свойств или матрицей. Матрица бинарного отношения на множестве A = а1 ,..., аm  – это квадратная матрица m×m = m2, в которой элементы сij. 1, если аi R aj, cij= 0, в противном случае, если ai Ra j . Представим, рассмотренные ранее Примеры 2.2, в матричной форме а) «меньше» или «равно» б) иметь «общий делитель отличный от единицы» в) быть «делителем» 1 2 3 1 1 2 1 1 3 1 1 1 1 2 3 1 2 1 3 1 1 2 3 1 1 2 1 1 3 1 1 Откуда следует, что отношения равенства задаются единичной матрицей. 2 Свойства Отношений 1. R – рефлексивно, то  аA оно допускает подобие элементов: aRa . Главная диагональ матрицы такого отношения содержит одни единицы, а у антирефлексивного – одни нули. Отношения «  »,«  »,«=» и «иметь общий делитель» – рефлексивны, а «<»,«>» и «быть сыном» – антирефлексивны. 2. Отношение R – симметрично, если aRb  bRа , а его матрица симметрична относительно главной диагонали. R – антисимметрично, если aRb  bRа возможно лишь при а = b. 3. R – транзитивно, если  a,b,cA а  b  с из aRb и bRc следует aRc. Отношения «=»,«  »,«  »,«<»,«>», «жить в одном городе» – транзитивны, отношение «быть сыном» – нетранзитивно. Транзитивность – это сохранение свойства в цепи отношений. Отношение «попарно пересекающиеся множества» нетранзитивно: {1,2} пересекается с {2,3}, {2,3} пересекаются с {3,4}, но {1,2}  {3,4} – пусто. Отношения порядка на множестве Наиболее употребляемыми бинарными отношениями на множестве вещественных чисел являются отношения порядка. Рефлексивное, транзитивное и антисимметричное отношение на множестве А определяет нестрогий порядок на А. Для представления нестрогого порядка на числовом множестве используется символ ≤, для обратного порядка – символ ≥. Отношение < (или >) определяет строгий порядок. Это отношение не удовлетворяет условию рефлексивности: хRх. Линейный порядок на множестве А для любых его двух элементов х и у означает выполнение одного из трёх отношений х < у, или х = у, или у < х. Непустое множество А, на котором зафиксирован линейный порядок, называется линейно упорядоченным множеством. Если в нестрого упорядоченном множестве А есть несравнимые элементы х и у, о которых нельзя сказать, что х  у или у  х, то такое множество называется частично упорядоченным. Диаграммы Хассе Любое нестрого упорядоченное множество А можно представить в виде схемы (диаграммы), в которой каждый элемент множества А изображается точкой плоскости. Если у покрывает элемент x (x < у), то точки х и у соединяются отрезком, причём точку, соответствующую х, располагают ниже у. Такие схемы называются диаграммами Хассе, При их построении используется правило следования, основанное на коде Грея. В этом коде соседние номера или числа (представленные в бинарной форме) различаются цифрой только в одной позиции. Например, (100) и (101). Пример 2.5. Пусть А = {0,1,2,3,4,5,6,7} – линейно упорядоченное множество с определённым на нём отношением нестрогого порядка ≤ на множестве целых положительных чисел, не превосходящих семи. В нём предыдущий элемент покрывается последующим. Его диаграмма Хассе изображена на рис. 2.1. Пример 2.6. Рассмотрим ещё одно отношение: Р = {(х, у)/ х, у  Z+, х ≤ у, 0 ≤ х ≤ 2, 0 ≤ у ≤ 2)}. Элементы этого отношения, упорядоченные пары чисел, будут упорядочены отношением покрытия: элемент (a,b) покрывается элементом (а,d), если выполняется отношение b < d; т.е. покрывается элементом (c,d), если (а = с) & (b ≤ d). Или элементом (c,d), если: (а ≤ c) & (b = d). 3 Рис. 2.1 Рис. 2.2 Проверим теперь, будет ли это множество нестрого упорядоченным. Перечислим его элементы: Р = {(0,0), (0,1), (0,2), (1,1), (1,2), (2,2)}. Отношение Р рефлексивно. Но (1,2)  Р , а (2,l)  P, следовательно, Р антисимметрично. Пусть теперь (х, у)  Р, (y, z)  Р. Если х  у и у  z и, следовательно, х  z, тогда (х, z)  Р, т.е. отношение Р транзитивно. Тогда Р – не строго упорядоченное множество. Его диаграмма Хассе на рис. 2.2. ТЕОРИЯ ГРАФОВ Теория графов – область дискретной математики, занимающаяся постановкой, исследованием и решением разнообразных проблем, которые могут быть описаны с помощью графических объектов, называемых графами. Графы могут формироваться на основе соответствий и отношений, т.е. графы в определённом смысле можно трактовать как графическую интерпретацию этих закономерностей, задавая вершины как точки плоскости или трёхмерного пространства, но координатная форма задания у них отсутствует. Каждый граф определяется заданием пары множеств V и E. Элементы vi первого множества V обычно изображаются точками плоскости или пространства и носят название вершин. Элементы eij  {vi , v j } второго множества E, устанавливающего связь между элементами первого, изображаются линиями, соединяющими соответствующие вершины графа. При этом требуется, чтобы линия была непрерывной и проходила только через те вершины, которые она соединяет, а для плоского графа требуется, чтобы эти линии могли пересекаться только в вершинах (линия Жордана) и не обязательно должна быть отрезком прямой. За всеми разновидностями этих линий установилось общее название – рёбра графа. Если рёбра, составляющие множество E, определяются, как упорядоченные пары, то это устанавливает определённый порядок перемещения от вершины к вершине. В этом случае, обобщённое понятие ребра уточняется, оно именуется дугой графа, а сам граф G(V , E ) определяется как ориентированный (орграф). Например, граф, представленный множеством вершин V :{v1 , v2 , v3 , v4 } и множеством рёбер: E :{(v1 , v2 ),(v1 , v3 ),(v1 , v3 ),(v3 , v2 ),(v2 , v4 ),(v3 , v4 ),(v1 , v1 ),(v1 , v2 )} – орграф. Рис. 2.3. Пример орграфа 4 Если ориентация не указана, то элементы E носят общее название – рёбра, а граф G(V , E ) считается неориентированным графом или норграфом. Существуют смешанные виды графов, в которых присутствуют как рёбра, так и дуги. Пара разнонаправленных дуг интерпретируется как ребро. Дуга, имеющая началом и концом одну и ту же точку, называется петлёй. Граф с петлями называется псевдографом. Если у графа есть дублирующиеся дуги, то такой граф называется мультиграфом. Пусть имеется множество V с элементами v (вершин). Рассматривая это множество, как носитель некоторого бинарного отношения R, сформируем декартов квадрат V2 на множестве V вершин. Примем его за унивёрсум, а график отношения R(v1,v2) на этом множестве V2, будет определять множество E дуг, направленных рёбер e1,2 = (v1,v2) графа G(v,e), как связи между вершинами v1 Rv 2 . Учитывая, что графы G , как и бинарные отношения R, представимы матрицами, то между ними можно установить взаимно однозначное соответствие. Этот факт легко усмотреть из идентичности матрицы антисимметричного бинарного отношения и матрицы смежности орграфа. Матрица бинарного отношения на множестве вершин графа является матрицей смежности графа. Матрица соответствия множества рёбер и множества вершин графа называется матрицей инцидентности графа. Построение графов Поскольку графическое изображение бинарного отношения приводит к понятию графа, то математически граф можно определить как пару множеств А и R, где А = ai  – множество вершин графа G; а симметричное отношение R  a ; a  i j – множество рёбер графа G. a1 a3 Здесь границы отрезков (кружки) обозначают элементы множества А, а соединяющие их линии указывают на связывающее элементы отношение R: a2 a4 a1 Ra 2 , a 2 Ra 4 и т.д. Но a3 Ra 4 , где R обозначает отсутствие отношения, т.е., что a3 , a4   R . Рис. 2.4. Диаграмма графа – графическое отображение бинарного отношения В теории графов используется геометрическое понятие инцидентности, обычно применяемое для установления принадлежности (связи) между точками, прямыми и плоскостями в аксиоматике Д. Гильберта. Граф геометрически может рассматриваться как совокупность множества точек и множества линий, между элементами которых определено соответствие (отображение) инцидентности, по которому каждый элемент графа r  R инцидентен (соответствует) ровно двум элементам vi , v j  V . Определение. Графом называют тройку G=(V,R,P), где V – множество вершин, R – множество рёбер графа (отношений на множестве вершин), Р – предикат 5 инцидентности вершин и рёбер графа. Р(vi,vj,r) = 1 означает, что вершины vi,vj  V смежны (связаны) между собой и инцидентны ребру r  R графа G. Рассматривая отношение пары вершин, как линию их соединяющую, назовём неупорядоченную пару вершин ребром, а упорядоченную пару – дугой. Графы изображают в виде диаграмм, на которых вершины изображаются точками (окружностями, прямоугольниками), а рёбра – отрезками необязательно прямых линий, соединяющими смежные вершины. Ориентированное ребро (дугу) изображают направленным отрезком. В частично ориентированном графе ориентированы не все рёбра. Граф называется абстрактным, если вершины его занумерованы, то граф называется маркированным или отмеченным. Если рёбрам графа ставят в соответствие числовые характеристики связи, то такие графы называются взвешенными. В этом случае матрица инцидентности содержит веса соответствующих связей, знак перед «весовым» числом связан с направлением ребра. Матричное представление графа Как уже было сказано, задать граф GV , R  – значит описать множество V его вершин и соответствующее множество R его рёбер. Соответствие этих множеств можно задать через отображение инцидентности I между их элементами. В связи с этим, каждое из этих двух множеств следует представить в виде списка, для чего необходимо упорядочить (произвольно) их элементы, пронумеровав вершины и рёбра. И граф записывается в виде G({v1,…,vn}; {r1,…,rm}). (2.1) N 1 2 3 4 5 6 7 8 9 10 Рисунок 2.5 I 1 1 1 II 1 1 1 III IV V VI 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 1 1 0 0 1 0 1 0 0 1 0 1 0 0 1 0 0 0 0 1 Таблица 2.1 VII 1 1 Классически отображение инцидентности определяется матрицей I   j 1, n i 1, m , размерности m×n. В m строках этой матрицы размещена информация о рёбрах, обозначенных индийскими цифрами, а в n столбцах – о вершинах, обозначенных римскими цифрами. Элементы этой матрицы формируются по следующему правилу: если в графе ребро еi инцидентно вершине vj, то εij = 1, и εij = 0 в противном случае. Так задаётся матрица инцидентности I неориентированного графа G. 6  Для ориентированного графа G формирование матрицы инцидентности отличается указанием направления дуги: если vj – начало дуги ri, то εij = –1; если vj – конец дуги ri, то εij = 1; отсутствие отображения инцидентности между элементами определяется как εij = 0. Если еi – петля, а vj – инцидентная ей вершина, то εij – любое число (чаще всего равное 2), но отличное от 1;0;–1. Так задаётся матрица  инцидентности ориентированного графа G , например, изображённого на рисунке 2.6. Соответствующая ему матрица инцидентности представлена таблицей 2.2. N 1 2 3 4 5 6 7 I -1 -1 II 1 -1 Рисунок 2.6 III IV V VI 0 0 0 0 1 0 0 0 0 1 0 0 -1 0 1 0 -1 0 0 1 -1 0 0 0 0 0 0 0 Таблица 2.2 VII 1 2 Следовательно, структура матрицы инцидентности не зависит от факта ориентированности графа, но направленность дуги можно определить по знаку соответствующего элемента матрицы. Матричное описание графа не ограничивается матрицей I. Если в исходной задаче, которую представляет граф и, соответственно, в описании графа основная информационная нагрузка ложится на вершины, то для определения графа используется матрица смежности S, элементы которой описывают граф через отношение связности его вершин. Это квадратная матрица S = ||δij|| размерности n2, строки и столбцы которой определяются вершинами графа. Для неориентированного графа δij равно количеству рёбер, инцидентных i-й и j-й вершинам. Для ориентированного графа этот элемент равен количеству дуг с началом в i-й вершине и концом в j-й. Подобное определение в общем случае соответствует мультиграфу. В дальнейшем по умолчанию будем рассматривать классические графы, где δij принимают значения 0 и 1. I II III IV V VI VII I 1 1 1 II III IV 1 1 0 0 0 1 0 0 1 1 1 0 0 1 0 1 0 1 0 0 0 Таблица 2.3 V 1 1 1 VI 1 1 1 VII 1 1 I II III IV V VI VII I II 1 III IV V 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 Таблица 2.4 VI 1 VII 1 1 7 Таким образом, матрица смежности неориентированного графа всегда симметрична, а у ориентированного графа симметрична только в том случае, если каждой его дуге соответствует другая дуга, идущая в противоположенном направлении. Матрицы смежности рассмотренных графов представлены в таблицах 2.3 и 2.4. Число вершин графа G равно числу строк (столбцов) матрицы смежности. Число рёбер G определяется суммой элементов верхней треугольной подматрицы матрицы смежности (в которую входят элементы матрицы смежности, расположенные над её  главной диагональю). Для G число дуг определяется количеством не нулевых элементов матрицы смежности. Итак, граф может быть представлен графически, множествами вершин и рёбер, матрицами описания: матрицей инцидентности, матрицей смежности. Граф считается полностью заданным, если задана его матрица смежности или инцидентности. В первом случае должна быть зафиксирована нумерация его вершин, во втором – фиксируются нумерации его вершин и рёбер (дуг). Графы, отличающиеся только нумерацией вершин, с сохранением отношения смежности называются изоморфными. 8