Изменения
Нет описания правки
# Можно ли в определении отношения эквивалентности убрать требование рефлексивности отношения, потому что оно следует из симметричности и транзитивности?
# 🤔 Транзитивный остов. Задано антисимметричное транзитивное отношение $R$ на $X$. Предолжите полиномиальный алгоритм построения отношения $S$, такого что $S^+=R$, причем в $S$ содержится минимальное число пар элементов.
# 🤔 В предыдущем задании требование антисимметричности транзитивности опустить нельзя. Задано антисимметричное отношение $R$ на $X$. Докажите, что если решить предыдущее задание для произвольного транзитивного существует полиномиальный алгоритм построения отношения$S$, такого что $S \subset R$ и $S^+=R^+$, причем в $S$ содержится минимальное число пар элементов, то можно проверить, есть ли в графе гамильтонов цикл (цикл, проходящий по каждой вершине графа ровно один раз) за полиномиальное время.
