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

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

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

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

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

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

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

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

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

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

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

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