Связное отношение

Свя́зное отноше́ние — бинарное отношение на множестве, связывающее в прямом или обратном порядке все пары различных элементов.

Более подробно, бинарное отношение $R$ на множестве $X$ называется связным, если для любых различных $x,y\in X$ выполняется хотя бы одно из условий $xRy$ или $yRx$:

$x\neq y\implies xRy\lor yRx$.

Таким образом, связность отношения $R$ эквивалентна тому, что для любых $x,y\in X$ выполняется хотя бы одно из трёх условий

$x=y$ или $xRy$ или $yRx$;

если же для любых $x,y\in X$ выполняется в точности одно из этих трёх условий, то говорят, что отношение $R$ удовлетворяет закону трихотомии (или обладает свойством трихотомии).

Отношение $R$ называется сильно связным, если оно связывает все пары (необязательно различных) элементов в прямом или обратном порядке, то есть если для любых $x,y\in X$ выполняется хотя бы одно из условий $xRy$ или $yRx$. Cильно связное отношение может быть определено эквивалентным образом как связное и рефлексивное отношение.

Примеры

Важнейшим примером связного отношения является отношение линейного порядка на множестве. Более точно,

• отношение строгого линейного порядка может быть охарактеризовано как отношение строгого частичного порядка, обладающее свойством связности (что более кратко выражают так: строгий линейный порядок — это связный строгий частичный порядок);
• отношение нестрогого линейного порядка на множестве может быть охарактеризовано как отношение нестрогого частичного порядка, обладающее свойством связности (или, что равносильно в данном случае, свойством сильной связности).

Отношение строгого линейного порядка является связным (и даже удовлетворяет свойству трихотомии), но не сильно связным.

Ориентированный простой граф является турниром в том и только в том случае, если отношение смежности его вершин связно.

Характеризации

Связное отношение

Для бинарного отношения $R$ на множестве $X$ следующие условия эквивалентны:

• $R$ связно;
• $U_{X}=R\cup \Delta _{X}\cup R^{-1}$;
• ${\overline {\Delta _{X}}}\subset R\cup R^{-1}$;
• ${\overline {R}}$ антисимметрично.

Здесь $U_{X}=X\times X$ — универсальное отношение, $\Delta _{X}=\{(x,x):x\in X\}$ — отношение равенства (диагональное отношение), $R^{-1}$ — отношение, обратное отношению $R$, а ${\overline {R}}=U_{X}\setminus R$ — дополнение (отрицание) отношения $R$. Из второго условия следует, что связное отношение толерантности (в частности, связное отношение эквивалентности) совпадает с универсальным отношением.

Сильно связное отношение

Для бинарного отношения $R$ на множестве $X$ следующие условия эквивалентны:

• $R$ сильно связно;
• $U_{X}=R\cup R^{-1}$;
• $R^{-1}\subset {\overline {R}}$;
• ${\overline {R}}$ асимметрично.

Второе условие показывает, что бинарное отношение на множестве $X$ связно тогда и только тогда, когда его симметричное замыкание совпадает с универсальным отношением на $X$; в частности, симметричное сильно связное отношение совпадает с универсальным.

Варианты терминологии

Иногда связным называют сильно связное отношение (связное отношение в таком случае называется слабо связным). Кроме того, вместо термина «сильно связное отношение» может употребяться термин «полное отношение» (в другой терминологии «полное отношение» является синонимом универсального). Иногда свойство связности отношения называют линейностью.

Литература

• Дубов Ю. А., Травкин С. И., Якимец В. Н. Многокритериальные модели формирования и выбора вариантов систем. — М.: Наука, 1986. — 294 с. — (Теория и методы систем анализа; 18).

• Мельников О. В., Ремесленников В. Н., Романьков В. А., Скорняков Л. А., Шестаков И. П. Общая алгебра / Под общ. ред. Л. А. Скорнякова. — М.: Наука, 1990. — Т. 1. — 500 с. — ISBN 5-02-014426-6.

• Новиков Ф. А. Дискретная математика. — 3-е. — М. [и др.]: Питер, 2017. — 493 с.

• Алескеров Ф. Е., Хабина Э. Л., Шварц Д. А. Бинарные отношения, графы и коллективные решения. — 2-е, перераб. и доп.. — М.: Физматлит, 2012. — 341 с. — ISBN 978-5-9221-1363-2.

Одним из источников, использованных при создании данной статьи, является статья из википроекта «Рувики» («ruwiki.ru») под названием «Связное отношение», расположенная по адресу: — «https://ru.ruwiki.ru/wiki/Связное_отношение» Материал указанной статьи полностью или частично использован в Циклопедии по лицензии CC-BY-SA 4.0 и более поздних версий. Всем участникам Рувики предлагается прочитать материал «Почему Циклопедия?».