Главная Вход в систему Регистрация
Задать вопрос Консультации Пользователи Форум
О системе Помощь
Задать вопрос экспертам
Консультация № 195814
05.06.2019, 22:43
0.00 руб.
0 3 0
Образование
Здравствуйте! Прошу помощи в следующем вопросе:

Отношение задано на множестве двузначных чисел
M=(11;45;39;87;86) : abRcd ⇔ a >= c, b = d. Выполните
следующие задания:
1. нарисуйте граф отношения и постройте матрицу
смежности этого графа;
2. определите, является ли отношение
рефлексивным, антирефлексивным, симметричным,
антисимметричным, асимметричным, транзитивным.
Дайте обоснование своим ответам;
3. определите, является ли это отношение отношением
эквивалентности, отношением порядка (строгого,
нестрогого, частичного, линейного); дайте
обоснование своему ответу;
4. ответьте, применим ли к этому отношению
алгоритм топологической сортировки; если алгоритм
применим, примените его; приведите протокол
работы алгоритма, интерпретируя его на графе
и матрице смежности (для определенности при
проверке, при наличии нескольких минимальных
элементов договоримся выбирать первый в
лексикографическом порядке); дайте объяснение
смыслу алгоритма топологической сортировки. В
качестве ответа привести линейно упорядоченные
элементы множества.

Первое задание выполнила.
получается такая матрица:
1 0 0 0 0
0 1 0 0 0
0 0 1 0 0
0 0 0 1 0
0 0 0 0 1
В графах получается, что каждая вершина образует петлю.
Получается такое соотношение обладает свойствами рефлексивности, симметричности и антисимметричности? Преподаватель говорит, что у меня неверно. И как тогда сделаь 3? В 4 топологическая сортировка неприменима?
Пожалуйста, помогите

Обсуждение

давно
karmapolozhitelnaya
Посетитель
403102
2
06.06.2019, 21:01
общий
Адресаты:
Определение противоречит самому себе. Отношение задано на парах чисел. Имеется в виду пары из MxM? Тогда в матрице отношения 25 строк и столбцов. И отношение не может быть симметричным и антисимметричным одновременно.
давно
karmapolozhitelnaya
Посетитель
403102
2
06.06.2019, 21:05
общий
Отношение антисимметрично, рефлексивно, транзитивно, является отношением частичного порядка.
давно
Лангваген Сергей Евгеньевич
Советник
165461
578
11.06.2019, 10:05
общий
11.06.2019, 11:09
Адресаты:
2. На множестве M abRcd <==> a=b, b=c (здесь a и с -- первые цифры, b и d вторые цифры).
Иначе говоря xRy <==> x = y, где x=ab, y = cd -- двузначные числа.

1) рефлексивность xRx, ДА;
2) антирефлексивность -- НЕТ;
3) симметричность xRy <==> yRx, ДА;
4) антисимметричность xRy & yRx ==> x=y, ДА;
4) асимметричность -- НЕТ, т.к. xRx;
5) транзитивность xRy & yRz ==> xRz, ДА;

3. R рефлексивно, симметрично и транзитивно,
поэтому является отношением эквивалентности на M.
Каждый элемент эквивалентен только самому себе.

R является отношеним нестрогого частичного порядка на M, так как оно рефлексивно,
антисимметрично и транзитивно. Каждый элемент сравним только с самим собой.

R рефлексивно, поэтому не является строим порядком.

R не является линейным порядком на M, т.к есть несравнимые элементы.
Форма ответа