Графы и частично упорядоченные множества (стр. 1 из 2)

Обе эти структуры являются частными случаями бинарных отношений. Пусть задано множество каких-то объектов и из этих объектов по какому-то определенному принципу формируются пары. Например, дано некоторое множество людей, а пары в нем выбираются по такому принципу: первый элемент пары - некий человек, а второй - один из его родителей. При этом один и тот же человек может присутствовать в двух и более парах, например, когда один и тот же человек имеет двоих, троих или более детей. Например, три пары в этом отношении (Иван, Мария), (Дарья, Мария), (Глеб, Мария) означают, что Иван, Дарья и Глеб - дети Марии. В качестве математического примера бинарного отношения можно привести пары, составленные из некоторого множества чисел, при этом первое число в каждой паре меньше второго. Это пример бинарного отношения "меньше". Другой пример: задана некоторая система множеств, а бинарное отношение в этой системе формируется из пар множеств по принципу: первое множество включено во второе множество - это пример бинарного отношения "включение множеств".

Существует много типов бинарных отношений с разными свойствами. Самым общим из этих типов является граф. Это произвольное бинарное отношение, но его особенностью является непривычная терминология - элементы множества, из которого формируются пары, называются вершинами, а сами пары в зависимости от их свойств носят названия ребра или дуги. Графы обычно изображаются не в виде таблицы с двумя колонками (каждая строка такой таблицы представляет пару элементов - вершин), а в виде схемы.

Рассмотрим пример. Пусть задано множество вершин

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<5<12<19. При линейном порядке все элементы частично упорядоченного множества можно выстроить в одну цепочку по заданному отношению.

В то же время существует немало множеств с отношением частичного порядка, среди которых имеются пары элементов, не связанные этим отношением. К таким множествам, в частности, относятся системы множеств, сравниваемых по включению. Например, если заданы три множества

P = {a, b, c}; Q = {b, d}; R = {a, b, c, d},

то для них линейный порядок установить невозможно, так как множества P и Q несравнимы - ни одно из них не включено в другое. В то же время, если множество Q в этой совокупности заменить на множество Q₁ = {b, c}, то мы получим линейный порядок

Q₁Ì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.