RUS  ENG
Полная версия
ЖУРНАЛЫ // Вестник Удмуртского университета. Математика. Механика. Компьютерные науки // Архив

Вестн. Удмуртск. ун-та. Матем. Мех. Компьют. науки, 2013, выпуск 4, страницы 3–12 (Mi vuu396)

Эта публикация цитируется в 6 статьях

МАТЕМАТИКА

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

Х. Ш. Аль Джабри, В. И. Родионов

Удмуртский государственный университет, 426034, Россия, г. Ижевск, ул. Университетская, 1

Аннотация: Любое бинарное отношение $\sigma\subseteq X^2$ (где $X$ – произвольное множество) порождает на множестве $X^2$ характеристическую функцию: если $(x,y)\in\sigma$, то $\sigma(x,y)=1$, а иначе $\sigma(x,y)=0$. В терминах характеристических функций на множестве всех бинарных отношений множества $X$ вводится понятие бинарного рефлексивного отношения смежности и определяется алгебраическая система, состоящая из всех бинарных отношений множества и из всех неупорядоченных пар различных смежных бинарных отношений. Если $X$ – конечное множество, то эта алгебраическая система – граф (“граф графов”).
Показано, что если $\sigma$ и $\tau$ – смежные отношения, то $\sigma$ является частичным порядком тогда и только тогда, когда $\tau$ является частичным порядком. Исследованы некоторые особенности строения графа $G(X)$ частичных порядков. В частности, если $X$ состоит из $n$ элементов, а $T_0(n)$ – это число помеченных $T_0$-топологий, определенных на множестве $X$, то количество вершин в графе $G(X)$ равно $T_0(n),$ а количество компонент связности равно $T_0(n-1)$.
Для всякого отношения частичного порядка $\sigma$ определяется понятие его опорного множества $S(\sigma)$, являющегося некоторым подмножеством множества $X$. Если $X$ – конечное множество, а частичные порядки $\sigma$ и $\tau$ принадлежат одной и той же компоненте связности графа $G(X)$, то равенство $S(\sigma)=S(\tau)$ имеет место тогда и только тогда, когда $\sigma=\tau$. Показано, что в каждой компоненте связности графа $G(X)$ совокупность опорных множеств ее элементов является специфическим частично упорядоченным множеством относительно естественного отношения включения множеств.

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

УДК: 519.175+519.115.5

MSC: 05C30

Поступила в редакцию: 13.08.2013



Реферативные базы данных:


© МИАН, 2024