Граф частичных порядков


ВЕСТНИК УДМУРТСКОГО УНИВЕРСИТЕТА

МАТЕМАТИКА. МЕХАНИКА. КОМПЬЮТЕРНЫЕ НАУКИ

МАТЕМАТИКА



2013. Вып.4

УДК 519.175 + 519.115.5


© X. Ш. Аль Джмбри, В. И. Родионов

ГРАФ ЧАСТИЧНЫХ ПОРЯДКОВ

Любое бинарное отношение ст С X² (где X — произвольное множество) порождает на множестве X² характеристическую функцию: если (х,у) С ст, то ст(х,у) = 1, а иначе ст(х,у) = 0. В терминах характеристических функций на множестве всех бинарных отношений множества X вводится понятие бинарного рефлексивного отношения смежности и определяется алгебраическая система, состоящая из всех бинарных отношений множества и из всех неупорядоченных пар различных смежных бинарных отношений. Если X — конечное множество, то эта алгебраическая система — граф («граф графов»).
   Показано, что если ст и т — смежные отношения, то ст является частичным порядком тогда и только тогда, когда т является частичным порядком. Исследованы некоторые особенности строения графа G(X) частичных порядке в. В частности, если X состоит из n элементов, a To(n) — это число помеченных Tq-топологий, определеиных на множестве X, то количество вершин в графе G(X) равно To(n), а количество компонент связности равно To(n — 1).
   Для всякого отношения частичного порядка ст определяется понятие его опорного множества S(a), X. X
порядки ст и т принадлежат одной и той же компоненте связности графа G(X), то равенство S(<t) = S(t) имеет место тогда ст только тогда, когда ст = т. Показано, что в каждой компоненте связности графа G(X) совокупность опорных множеств ее элементов является специфическим частично упорядоченным множеством относительно естественного отношения включения множеств.

Ключевые слова: бинарное отношение, граф, частичный порядок, конечная топология.

   1.    Смежность бинарных отношений. Пусть B = {0,1} — булево nтожество, X — произвольное множество, а X² = X х X. Всякое подмножество ст С X², называемое бинарным отношением (или просто отношением) на множестве X, порождает характеристическую функцию
X» : X² н B,   X»(х,у) = { ₀’       !(’У) С ст’
                                               о, (X(x,y) с ст.
Далее функцию х»(х, у) будем обозначать через ст(х,у). На множестве 2X² всех бинарных отношений множества X введем бинарное рефлексивное отношение смежности.

  Определение 1. Пусть X = Y U Z — дизъюнктное объединение двух подмножеств (допускается, что Y = 0 ил и Z = 0). Предположим, что отношение ст С X² таков о, что ст(х,у) = 0 для всех (х, у) С Y х Z. Оно порождает отношение т С X² такое, что
т(х, у) = 1 — ст(у, х) для всех (х, у) С Y х Z, т(х, у) = 0 для всех (х, у) С Z х Y, т(х, у) = ст(х, у) для всех (х, у) С Y² U Z².
           т                                 ст.

т                     ст,
,              "                      Y xZ
и ст смежно с т, и этот факт мы записываем в виде диаграммы ст <-т т, или

Y
Z

YZ

ст(x,y)

Y xZ ----Т Т =

  Y     Z     
Y   1-ст (y,x)
Z 0           

0

= а

Здесь и далее в диаграммах мы отмечаем значения характеристических функций в тех точках, которые априори известны (например, в блоке Y х Z для отношения ст пишем «обобщенный» 0,                  ст(х, у) = 0       (х, у) С Y х Z,                                 т
пишем 1 — ст (у, х), и это означает, что т(х, у) = 1 — ст (у, х) для всех (х, у) С Y х Z).