Графы и частично упорядоченные множества

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

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

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

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) = Æ.

Если мы, используя изображение произвольного графа, будем двигаться от вершины к вершине в соответствии с направлением дуг (при этом по ребру можно передвигаться в любую сторону), то последовательность вершин, отмечаемых по мере такого "обхода", называется путем в данном графе. ............