http://neerc.ifmo.ru/wiki/api.php?action=feedcontributions&user=188.170.74.186&feedformat=atomВикиконспекты - Вклад участника [ru]2024-03-28T08:51:38ZВклад участникаMediaWiki 1.30.0http://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D0%BF%D0%B8%D1%81%D0%BE%D0%BA_%D0%B7%D0%B0%D0%B4%D0%B0%D0%BD%D0%B8%D0%B9_%D0%BF%D0%BE_%D0%94%D0%9C_2019_%D0%BE%D1%81%D0%B5%D0%BD%D1%8C&diff=71793Список заданий по ДМ 2019 осень2019-09-10T16:00:37Z<p>188.170.74.186: Новая страница: «# Пусть $R$ и $S$ - рефлексивные отношения на $A$. Будет ли рефлексивным их а) объединение? б) пе…»</p>
<hr />
<div># Пусть $R$ и $S$ - рефлексивные отношения на $A$. Будет ли рефлексивным их а) объединение? б) пересечение? В этом и следующих заданиях, если ответ отрицательный, при демонстрации контрпримера удобно использовать представление отношения в виде ориентированного графа.<br />
# Пусть $R$ и $S$ - симметричные отношения на $A$. Будет ли симметричным их а) объединение? б) пересечение?<br />
# Пусть $R$ и $S$ - транзитивные отношения на $A$. Будет ли транзитивным их а) объединение? б) пересечение?<br />
# Пусть $R$ и $S$ - антисимметричные отношения на $A$. Будет ли антисимметричным их а) объединение? б) пересечение?<br />
# Напомним, что композиция отношений $R$ и $S$ это отношение $T=RS$, где $xTy$, если найдется $z$, такой что $xRz$ и $zRy$. Пусть $R$ и $S$ - транзитивные отношения на $A$. Будет ли транзитивной их композиция?<br />
# Пусть $R$ и $S$ - антисимметричные отношения на A. Будет ли антисимметричной их композиция?<br />
# Определим $R^{-1}$ следующим образом: если $xRy$, то $yR^{-1}x$. Выполнено ли соотношение $RR^{-1} = I$, где $I$ - отношение равенства? Выполнен ли закон сложения степенией $R^iR^j=R^{i+j}$, если $i$ и $j$ разного знака?<br />
# Пусть $R$ обладает свойством $X$. Будет ли обладать свойством $X$ отношение $R^{-1}$? Следует проанализировать $X$ - рефлексивность, антирефлексивность, симметричность, антисимметричность, транзитивность<br />
# Постройте пример рефлексивного, симметричного, но не транзитивного отношения<br />
# Постройте пример рефлексивного, антисимметричного, но не транзитивного отношения<br />
# Постройте пример отношения, которое не симметрично и не антисимметрично<br />
# Постройте пример отношения, которое симметрично и антисимметрично<br />
# Является ли отношение $R$, такое что $(a, b) R (c, d)$, если $ad = bc$ на ${\mathbb Z}^+ \times {\mathbb N}$ отношением эквивалентности?<br />
# Может ли отношение частичного порядка быть отношением эквивалентности? Если да, то в каких случаях?<br />
# Можно ли в определении отношения эквивалентности убрать требование рефлексивности отношения, потому что оно следует из симметричности и транзитивности?<br />
# Транзитивный остов. Задано антисимметричное транзитивное отношение $R$ на $X$. Предолжите полиномиальный алгоритм построения отношения $S$, такого что $S^+=R$, причем в $S$ содержится минимальное число пар элементов.<br />
# В предыдущем задании требование транзитивности опустить нельзя. Задано антисимметричное отношение $R$ на $X$. Докажите, что если существует полиномиальный алгоритм построения отношения $S$, такого что $S \subset R$ и $S^+=R^+$, причем в $S$ содержится минимальное число пар элементов, то можно проверить, есть ли в графе гамильтонов цикл (цикл, проходящий по каждой вершине графа ровно один раз) за полиномиальное время.</div>188.170.74.186