Графы и частично упорядоченные множества
Обе эти структуры являютсячастными случаями бинарных отношений. Пусть задано множество каких-то объектови из этих объектов по какому-то определенному принципу формируются пары. Например,дано некоторое множество людей, а пары в нем выбираются по такому принципу: первыйэлемент пары — некий человек, а второй — один из его родителей. При этом один итот же человек может присутствовать в двух и более парах, например, когда одини тот же человек имеет двоих, троих или более детей. Например, три пары в этомотношении (Иван, Мария), (Дарья, Мария), (Глеб, Мария) означают, что Иван,Дарья и Глеб — дети Марии. В качестве математического примера бинарногоотношения можно привести пары, составленные из некоторого множества чисел, приэтом первое число в каждой паре меньше второго. Это пример бинарного отношения«меньше». Другой пример: задана некоторая система множеств, абинарное отношение в этой системе формируется из пар множеств по принципу: первоемножество включено во второе множество — это пример бинарного отношения «включениемножеств».
Существует много типов бинарныхотношений с разными свойствами. Самым общим из этих типов является граф. Этопроизвольное бинарное отношение, но его особенностью является непривычнаятерминология — элементы множества, из которого формируются пары, называютсявершинами, а сами пары в зависимости от их свойств носят названия ребра илидуги. Графы обычно изображаются не в виде таблицы с двумя колонками (каждаястрока такой таблицы представляет пару элементов — вершин), а в виде схемы.
Рассмотрим пример. Пусть задано множествовершин
V = {a, b, c, d, e},
из которого сформированонекоторое множество пар
E = { (a, b), (a,c), (b, d), (c, a), (c, e) }.
Множество пар E,сформированное из множества V вершин, является примеромбинарного отношения. Преобразуем это бинарное отношение в схему. Для этогоизобразим на листе бумаги все его вершины произвольным образом и соединим этивершины линиями со стрелками так, чтобы каждая стрелка выходила из первогоэлемента пары и входила во второй элемент пары (см. рисунок 1). При этом, еслиокажется, что некоторая пара вершин соединяется стрелкой в одну и в другуюсторону, то мы вместо линий со стрелками нарисуем линию без стрелок (для нашегопримера это пары (a, c) и (c, a)). С учетом этого дугами в графе являютсясоединительные линии со стрелками в одну сторону, а ребрами — соединения безстрелок или со стрелками, направленными в обе стороны. Можно считать, чтокаждое ребро содержат пару разнонаправленных дуг.
/>
Рис.1
Каждая дуга графа представленаначальной и конечной вершинами. Граф, у которого все связи представлены толькоребрами, называется неориентированным графом (или просто графом). Граф, укоторого отсутствуют ребра (т.е. все связи имеют только одно направление),называется ориентированным графом, а граф, у которого имеются и ребра, и дуги — смешанным.
Если задан граф G, то выражениеG (x), где x — произвольная вершина графа, используется для обозначениямножества смежных с ней вершин, т.е. вершин, в которые направлена дуга из x. Например,для графа G на рисунке 8 справедливы следующие равенства:
G (a) = {b, c}; G (b) = {d}; G (c)= {a, e}; G (d) = G (e) = Æ.
Если мы, используя изображениепроизвольного графа, будем двигаться от вершины к вершине в соответствии снаправлением дуг (при этом по ребру можно передвигаться в любую сторону), топоследовательность вершин, отмечаемых по мере такого «обхода», называетсяпутем в данном графе. Например для графа G на рисунке 8 существуют следующиепути: (a, b, d); (c, e); (a, c, a, b) и т.д. Пути можно записывать, используястрелки, например, a®b®d. При этом возможны графы, у которыхимеются самопересекающиеся пути, т.е. некоторые вершины и дуги могут внекоторых путях повторяться.
Циклом в графе называется такойпуть, когда его начальная и конечная вершина совпадают.
Например, в графе на рисунке 8имеется один цикл, обусловленный тем, что в нем имеется ребро (a, c). Поэтомуцикл можно представить в виде пути (a, c, a). Если вэтот граф добавить еще одну дугу (d, a),то в этом случае появится еще одни цикл (d, a, b, d). Посути цикл — это путь без начала и конца, поскольку, «путешествуя» поциклу, мы можем крутиться в нем бесконечное число раз.
Одним из основных в теорииграфов является понятие достижимости. Вершина yграфа G называетсядостижимой из вершины x, если в G существует путь из вершины x в вершину y. Частобывает необходимо определить для каждой вершины графа G множество всехдостижимых из нее вершин. Например, для вершины a вграфе на рисунке 1 достижимыми являются все вершины этого графа (в том числе исама вершина a), в то время как из вершины b достижима только одна вершина — d,а для вершины e в данном графе нет вообще достижимыхвершин.
Любое бинарное отношение можнопредставить как граф. Математические свойства графов часто используются примоделировании и анализе сложных систем частично упорядоченных множеств.
Частично упорядоченное множество- один из типов бинарного отношения. Отношение частичного порядка являетсяодним из фундаментальных общематематических понятий и широко используется втеоретической математике, в системах логического вывода и во многих другихприложениях. Оно является обобщением таких широко известных бинарных отношенийкак «меньше или равно» (£)для чисел и «включено или равно» (Í)для множеств. Обозначение "£"часто используется не только для обозначения отношения «меньше или равно»на множестве чисел, упорядоченных по величине, но и для обозначенияпроизвольного отношения частичного порядка. Формально отношение частичногопорядка определяется как заданное на множестве X бинарноеотношение со следующими свойствами:
рефлексивности: a£a для любого aÎX;
транзитивности: если a£b и b£c,то a£c;
антисимметричности: из a£b и b£aследует a=b,
где a, b и c — произвольные элементы частично упорядоченного множества X.
Среди всех отношений частичногопорядка наиболее простым в структурном отношении является линейный порядок,когда для любой пары разных элементов (a, b) множества определено либо a£b, либо b£a. Примерами линейного порядка являются множества чисел,упорядоченных по величине, и множества слов, расположенных в лексикографическомпорядке. Их можно по заданному порядку сформировать в виде одной непрерывнойпоследовательности. Например, 2
В то же время существует немаломножеств с отношением частичного порядка, среди которых имеются пары элементов,не связанные этим отношением. К таким множествам, в частности, относятсясистемы множеств, сравниваемых по включению. Например, если заданы тримножества
P = {a, b, c}; Q = {b, d}; R = {a, b, c, d},
то для них линейный порядокустановить невозможно, так как множества P и Q несравнимы — ни одно из них не включено в другое. В то жевремя, если множество Q в этой совокупности заменить намножество Q1 = {b, c}, то мы получим линейный порядок
Q1Ì P Ì R или {b, c}Ì{a, b, c}Ì{a, b, c, d}.
Еще одним широко известнымотношением частичного порядка является порядок по делимости. Предположим,задано некоторое множество положительных целых чисел (например, D = {1, 2, 3.4, 6, 12}. Тогда будем считать, что для двухчисел x и y верно x£y, если и только если число y делитсябез остатка на число x.
Для заданного множества D порядок по делимости верен для пар (1,2); (2,4); (3,6) и т.д.,Но для некоторых пар (например, (4,6)) такой порядок не соблюдается, так какчисло 6 не делится без остатка на число 4. Нетрудно убедиться, что отношениепорядка по делимости полностью соответствует свойствам частично упорядоченныхмножеств (рефлексивности, транзитивности и антисимметричности).
В математике известно немалоструктур, соответствующих частичному порядку. Рассмотрим некоторые общиесвойства отношений частичного порядка. Далее в целях сокращения будемиспользовать вместо термина «частично упорядоченное множество» термину-множество — своеобразная калька с эквивалентного английского термина poset.
Любое у-множество можнопредставить как ориентированный граф, в котором дуга a®b между парой элементов означает a£b. Однако не любой ориентированный граф является представлениему‑множества. Чтобы сугубо ориентированный граф представлял правильное у‑множество,необходимо и достаточно чтобы в нем не было циклов.
В математической литературеу-множества обычно изображаются в виде неориентированных графов (рис.2), приэтом подразумевается, что предшествующие элементы расположены ниже последующих.Поэтому, если в этих схемах правильно заменить ребра на дуги, то все дугиокажутся направленными снизу вверх.
/>
Рис.2
На этих рисунках показаны не всесвязи между элементами — те, которые следуют из свойства транзитивности (например,связь p®s на каждом из этих рисунков),в них отсутствуют. Такое сокращенное представление у‑множеств безтранзитивных связей называется диаграммой Хассе.
В дальнейшем мы будем изображатьчастично упорядоченные множества не так как это принято в математическихработах по алгебре (см. рисунок 2), а в виде ориентированных графов. Определимнаименьший и наибольший элементы у-множеств.
Наименьшим элементом у-множестваM (если он существует) называется элемент y такой, что y£a для любого элемента aÎM.
Наибольшим элементом у-множестваM (если он существует) называется элемент y такой, что a£y для любого элемента aÎM
Например, в у-множестве,изображенном на рис.2, b, нет ни наибольшего, ни наименьшего элементов, наименьшийэлемент (p) имеется в у‑множествах, изображенных на рис.2, a, c, d, анаибольший элемент имеется только в у‑множествах, изображенных на рисунке2, a, c.
Если в качестве отношениячастичного порядка мы выберем отношение включения, то в этом отношениинаименьшим элементом является пустое множество (Æ)(оно включено в любое множество), а наибольшим является универсум (в неговключено любое множество системы).
Рассмотрим два очень важныхпонятия теории у-множеств, которые позволяют существенно облегчить решениенекоторых задач анализа рассуждений. Это верхние и нижние конусы. Пусть A — произвольноеподмножество у‑множества M (т.е. A Í M). Определим для множества A верхний и нижний конусы.
Нижним конусом /> множества A называетсямножество всех таких элементов x, принадлежащих множеству M, каждый из которыхбудет меньше или равен (£) относительнолюбого элемента a, принадлежащего множеству A.
Верхним конусом /> множества A называетсямножество всех таких элементов x, принадлежащих множеству M, для каждого изкоторых любой элемент из множества A будет меньше илиравен (£) ему.
Нижний и верхний конусы можноопределять не только для подмножеств, но и для элементов у‑множества M. Еслиу-множество изображено в виде ориентированного графа, то верхний и нижний конусдля любого элемента X можно «вычислить», используясвойство достижимости:
верхний конус элемента X — это множество элементов, в этомножество входит сам элемент X и все элементы,достижимые из X;
нижний конус элемента X — это множество элементов, в этомножество входит сам элемент X и все элементы, изкоторых X достижимо.
Например, на множестве чисел M ={2, 4, 5, 7}, упорядоченном по величине, нижним конусом числа 4 являетсямножество {2, 4}, а верхним — {4, 5, 7}. Если рассмотреть у‑множество,показанное на рисунке 9, b, то
/>={p,q, r} и /> = {r,s, t, u}.
Далее мы рассмотрим две теоремы,связанные с конусами. C помощью первой теоремы можно вычислить верхние и нижниеконусы не для отдельных элементов, а для некоторых их совокупностей. По смыслуверхние конусы для некоторого множества M элементовдолжны содержать такие элементы, которые одновременно достижимы из каждогоэлемента множества M. Аналогично, если вычисляетсянижний конус для множества M, то он должен содержатьтакие элементы, каждый из которых предшествуют любому элементу из множества M. Тогда верхний и нижний конусы для этого множествавычисляются в соответствии со следующей теоремой.
Теорема. Пусть в произвольному-множестве выбрано некоторое подмножество M = {q1, q2,… qn} его элементов. Тогда
(i) MD= />Ç/>Ç… Ç/>;
(ii) MÑ=/>Ç/>Ç… Ç/>.
Доказательство. Пусть mi — произвольный элемента множества MD. Чтобы для каждого qk (qkÎ M) соблюдалось условие qk £ mi, необходимо и достаточно, чтобы элемент mi содержался в верхнем конусе каждого изэлементов множества M. А это означает, что элемент mi содержится в пересечении />Ç/>Ç… Ç/> верхних конусов всех этихэлементов. Аналогично, если mi — произвольныйэлемента множества MÑ,то для каждого qk (qkÎ M) соблюдается условие mi £ qk, а это означает, что элемент miсодержится в нижнем конусе каждого из элементов множества M.Следовательно, все элементы множества MÑ должны находиться в пересечении />Ç/>Ç… Ç/> нижних конусов. Конецдоказательства.
Для лучшего пониманиясоотношений, связанных с конусами, рассмотрим граф, изображающий диаграммуХассе некоторого у-множества (рисунок 3).
/>
Рис.3
По этому рисунку можно,используя свойство достижимости, легко вычислить верхние и нижние конусы любыхэлементов. Например,
RD={R, G, F,Q}
(элемент Rсодержится в верхнем конусе по определению, а остальные элементы введены какдостижимые из R);
MD={M, N, G,F, Q}; DD={D}; CD={C, D}; DÑ = {D, C, A}
(элемент Dсодержится в нижнем конусе по определению, а элементы Cи A введены в нижний конус, поскольку из них достижимэлемент D);
RÑ = {R, A}; MÑ = {M}; CÑ = {C, A}, GÑ = {G, M, R, A}.
Зная верхние или нижние конусыэлементов, можно по теореме легко вычислить соответственно верхние и нижниеконусы для множеств, состоящих их этих элементов. Например,
{R, M}D= RDÇ MD={R, G, F,Q}Ç{M, N, G, F, Q}={G, F, Q};
{R, C}D= RDÇ CD={R, G, F,Q}Ç{C, D}= Æ
(посмотрев на рисунок 10, можноубедиться, что в графе нет ни одной вершины, которая достижима как из R, так и из C);
{R, M}Ñ= RÑÇ MÑ={R, A}Ç{M}= Æ;
{R, C}Ñ= RÑÇ CÑ={R, A }Ç{C, A}= {A}.
Рассмотрим еще одно соотношение,связанное с конусами.
Теорема 2. Пусть r и q — различныеэлементы у-множества, при этом r £q. Тогда для верхних и нижних конусов этих элементов соблюдаются соотношения />Í/> и />Í/>.
Доказательство. Данныесоотношения следуют из определений верхних и нижних конусов. Если r £ q, то это означает, что q содержится в /> и,следовательно, все элементы из /> такжесодержится в />. В то же время в нижнихконусах наоборот: если r £ q, тоэто означает, что r содержится в /> и, следовательно, всеэлементы из /> также содержится в />. Конец доказательства.
Например, для у-множества,изображенного на рисунке 3, элементы A и G — сравнимы, т.е. A £ G (элемент Aпредшествует элементу G). Построим верхние и нижниеконусы этих элементов:
AD = {A,C, D, R,G, F, Q}; GD= {G, F, Q}; AÑ= {A}; GÑ = {G, R, A, M}.
Сравнивая эти конусы по включению,мы увидим, что в соответствии с теоремой 2 соблюдаются следующие соотношения: GD Í AD и AÑ Í GÑ.Если же выбрать для анализа пару элементов, для которых отношение £ не имеет места (например,элементы Q и N на рисунке 3),то мы увидим, что для них, соотношения, сформулированные в теореме 2, не верны.
Для анализа E-структур оченьважными являются еще два понятия — минимальные и максимальные элементы. Суть втом, что они существенно отличаются от наименьшего и наибольшего элементов. Начнемс минимальных элементов. Как мы уже знаем, если в структуре существуетнаименьший элемент, то он меньше любого другого элемента этого у‑множества.Но существуют элементы (в алгебре их иногда называют атомами), которые большенаименьшего, но при этом обладают одним удивительным свойством. Предположим,что элемент A — атом, а Xi произвольный элемент этого у-множества, кроменаименьшего. Тогда при сравнении атома A с любымэлементом Xi возможны только два варианта:
1) A £ Xiлибо 2) элементы A и Xiнесравнимы. Атомы в отличие от наименьших элементов называются минимальнымиэлементами.
Чтобы лучше понять эторассмотрим рисунок 10. Видно, что в этом у-множестве наименьшего элемента несуществует, так как ни один элемент в нем не обладает тем свойством что онпредшествует любому элементу. Например, элементу A непредшествует ни один элемент, но при этом он сам не предшествует такимэлементам как M и N (т.е. пары(A, N) и (A,M) не сравнимы, так как неизвестно, какой из элементовв каждой из этих пар является предшественником другого). Поэтому элемент A можно считать минимальным (но не наименьшим!) элементом. Нетрудновидеть, что в этой же структуре есть еще один минимальный элемент — M, который обладает теми же свойствами, что и элемент A.Т. е. в этой структуре существуют два минимальных элемента(хотя наименьшего в ней нет). Если в структуре имеется наименьший элемент, то вэтом случае минимальными элементами являются другие элементы, которые большенаименьшего, но при этом непосредственно примыкают к нему.
Максимальные элементы ву-множествах определяются аналогично. Максимальные элементы (в алгебре онииногда называются коатомами) — это элементы, обладающие следующими свойствами:
1) если наибольший элементсуществует, то максимальные элементы непосредственно предшествуют наибольшемуэлементу;
2) любой элемент у‑множества(кроме наибольшего) либо предшествует максимальному элементу, либо не сравним сним.
Посмотрев на у-множество нарисунке 10, можно с учетом этих свойств легко определить его максимальныеэлементы: это D, F и Q.