транзитивные отношения на множестве

[gris]

По моим познаниям бинарное отношение $R$ транзитивно, если $aRb \land bRc \Rightarrow aRc$.
Если в множестве нет ни одной тройки $a,b,c: aRb \land bRc$, то отношение всё равно же будет транзитивным? Но нет ли какого-то для него особого названия?
Я не помню и не нашёл

[mihaild]

Да, транзитивным будет. Это получится отношение связности на двудольном графе.

[gris]

Спасибо. Я в графах не очень:(
Понятно, что на двудольном графе не может быть транзитивных троек. А отношение связности транзитивно. Поэтому не может быть и троек кандидатов на транзитивность вида $(a,b,c): aRb \land bRc$ .
Но все ли такие отношения (без троек-кандидатов) можно представить в виде связнного двудольного графа? Например, если отношение представлять в виде матрицы, то матрица из нулей или матрица с единицами только по диагонали будут представлять транзитивные отношения. Разве что каждый элемент будет отдельной компонентой?
Вообще это из школьного листочка по комбинаторике: сколько на множестве из $k$ элементов существует отношений симметричных, рефлексивных, транзитивных и так далее. Я бы транзитивные отношения без транзитивных троек назвал полутранзитивными и посчитал

[mihaild]

Пардон, не связности, а смежности
Точное утверждение такое: назовем тройку $a, b, c$, такую что $aRb \wedge bRc$ транзитивной. Отношение без транзитивных троек есть отношение смежности для некоторого двудольного орграфа, в котором все ребра ориентированы из одной доли в другую.
(крайне глубокое утверждение, хороший конкурент доказательству формулы Ньютона-Лейбница через формулу Стокса)

gris в сообщении #1482086 писал(а):

Но все ли такие отношения (без троек-кандидатов) можно представить в виде связнного двудольного графа?

Связного - совсем не обязательно. Например пустое отношение.
Если не требовать связности - то да. Просто возьмем в левую долю все элементы, которые встречаются в отношении слева, а в правую - все остальные.

gris в сообщении #1482086 писал(а):

матрица с единицами только по диагонали

Для неё есть "транзитивные тройки".

[provincialka]

Когда рассуждаешь о транзитивности, полезно разобраться с рефлексивностью, точнее, с элементами $a, aRa$. "Тройка" же не предполагает, что ее элементы различны.

[gris]

Ой, мы сегодня рассматривали кучу вариантов. И называли свойства, и строили примеры, и обсчитывали их на паскале напрямую и монтекарлой. Интересно, однако! До тернарных отношений не дошли пока.
А насчёт троек да, можно называть тройки транзитивными разной степени транзитивности