Максимальные совместимые подмножества

@Leon_java · Регистрация: 01.10.2016

Author24 — интернет-сервис помощи студентам

Дали мне задание по дискретной математике, которую я вообще понять не могу, в интернете найти объяснению нет...понять не могу как делать, само задание

На множестве X задано отношение несовместимости R. Построить все максимальные совместимые подмножества множества X

Байт · 04.11.2016, 21:41

Что значит "совместимые"? Те, которые не являются "несовместимыми", т.е. не состоят в заданном отношение?
Ладно, для пары можно понять так. А что значит "подмножество совместимых элементов"? Это подмножество, все пары элементов которого совместимы? Так7

@Leon_java · 04.11.2016, 22:38 **[ТС]**

Получается так, ибо сам я тоже понять не могу этот вопрос, думал тут помогут его хотя бы разобрать....

Байт · 04.11.2016, 22:47

Сообщение от Leon_java

думал тут помогут его хотя бы разобрать....

Будем считать, что все так, как я предположил. Тогда отношение "совместимость" - это дополнение заданного вам отношения "несовместимость". Дополнение, значит там где были единички - станут нолики и наоборот. (на главной диагонали тоже единички.
Нарисуйте его, посмотрим.

@Leon_java · 04.11.2016, 23:43 **[ТС]**

Если я правильно понял, то получилось так но что это значит? что дальше?

Байт · 04.11.2016, 23:56

Сообщение от Leon_java

что дальше?

Теперь ищем группы элементов, совместимые между собой.
Вот одна из них: X1 X2. она максимальна - присоединить никого уже нельзя. Х4 несовместимо с Х2, остальные несовместимы с Х1
Вот еще одна: Х2 Х5 Х6
Другие ищите сами.

@Leon_java · 05.11.2016, 00:14 **[ТС]**

Спасибо, видимо это и есть ответ, большое спасибо) в поисковых я не смог найти такое как и в других книжках, либо я просто плохо искал хех))) еще раз спасибо

@Hacker1995 · 05.11.2016, 02:02

Доброй ночи!
У меня такое-же задание. Я понял как решать, Ваш ответ мне помог. У меня есть вопрос. Если мы нашли максимально-совместимые подмножества ( получились {x1, x2}, {x1, x4}, {x2, x5, x6 }, {x4, x3} ). То, это упорядоченные множества, или нет? То есть, надо ли находить еще и {x2, x1}, {x4, x1}, {x5,x2,x6} ... итд. ?
И есть сомнения по поводу прочерков. Их действительно надо заменять, или оставить? Может ли x1 например быть соовместимым с самим собой? - кажется странным. Определение отношения совместимости нашел, но там для двух разных множеств.
Спасибо!

Байт · 05.11.2016, 10:02

Сообщение от Hacker1995

И есть сомнения по поводу прочерков. Их действительно надо заменять, или оставить? Может ли x1 например быть соовместимым с самим собой? - кажется странным. Определение отношения совместимости нашел, но там для двух разных множеств.

Признаюсь честно. Понятие "отношение (не-)совместимости" встречаю впервые. Сейчас слегка погуглил - да, есть такое в логике. Но я подошел к этому, как алгебраист. Вот, есть какое-то отношение (подмножество прямого квадрата базового множества). Видимо, оно же без приставки "не" обозначает его дополнениние. А в дополнение входит главная диагональ. Не нравится такой подход? И не надо. Не включайте. На дальнейшее это не должно оказать никакого действия.

Сообщение от Hacker1995

это упорядоченные множества, или нет? То есть, надо ли находить еще и

Нет. Не надо. Понятие множества само по себе не предполагает наличия на на нем порядка.
Вот множество подмножеств, оно - да, на нем есть естественный порядок (не линейный). Потому-то вас и просят найти МАКСИМАЛЬНЫЕ совместимые подмножества.

@Leon_java 0 / 0 / 0 Регистрация: 01.10.2016 Сообщений: 37
		1
	Максимальные совместимые подмножества 04.11.2016, 17:38. Показов 4080. Ответов 8 Метки нет (Все метки) Дали мне задание по дискретной математике, которую я вообще понять не могу, в интернете найти объяснению нет...понять не могу как делать, само задание На множестве X задано отношение несовместимости R. Построить все максимальные совместимые подмножества множества X Миниатюры 0

Байт Диссидент 27706 / 17322 / 3812 Регистрация: 24.12.2010 Сообщений: 38,979
	04.11.2016, 21:41	2
	Что значит "совместимые"? Те, которые не являются "несовместимыми", т.е. не состоят в заданном отношение? Ладно, для пары можно понять так. А что значит "подмножество совместимых элементов"? Это подмножество, все пары элементов которого совместимы? Так7 1

@Leon_java 0 / 0 / 0 Регистрация: 01.10.2016 Сообщений: 37
	04.11.2016, 22:38 [ТС]	3
	Получается так, ибо сам я тоже понять не могу этот вопрос, думал тут помогут его хотя бы разобрать.... 0

Байт Диссидент 27706 / 17322 / 3812 Регистрация: 24.12.2010 Сообщений: 38,979
	04.11.2016, 22:47	4
	Сообщение от Leon_java думал тут помогут его хотя бы разобрать.... Будем считать, что все так, как я предположил. Тогда отношение "совместимость" - это дополнение заданного вам отношения "несовместимость". Дополнение, значит там где были единички - станут нолики и наоборот. (на главной диагонали тоже единички. Нарисуйте его, посмотрим. 0

@Leon_java 0 / 0 / 0 Регистрация: 01.10.2016 Сообщений: 37
	04.11.2016, 23:43 [ТС]	5
	Если я правильно понял, то получилось так но что это значит? что дальше? Миниатюры 0

Байт Диссидент 27706 / 17322 / 3812 Регистрация: 24.12.2010 Сообщений: 38,979
	04.11.2016, 23:56	6
	Сообщение было отмечено Leon_java как решение Решение Сообщение от Leon_java что дальше? Теперь ищем группы элементов, совместимые между собой. Вот одна из них: X1 X2. она максимальна - присоединить никого уже нельзя. Х4 несовместимо с Х2, остальные несовместимы с Х1 Вот еще одна: Х2 Х5 Х6 Другие ищите сами. 1

@Leon_java 0 / 0 / 0 Регистрация: 01.10.2016 Сообщений: 37
	05.11.2016, 00:14 [ТС]	7
	Спасибо, видимо это и есть ответ, большое спасибо) в поисковых я не смог найти такое как и в других книжках, либо я просто плохо искал хех))) еще раз спасибо 0

@Hacker1995 0 / 0 / 0 Регистрация: 09.02.2015 Сообщений: 8
	05.11.2016, 02:02	8
	Доброй ночи! У меня такое-же задание. Я понял как решать, Ваш ответ мне помог. У меня есть вопрос. Если мы нашли максимально-совместимые подмножества ( получились {x1, x2}, {x1, x4}, {x2, x5, x6 }, {x4, x3} ). То, это упорядоченные множества, или нет? То есть, надо ли находить еще и {x2, x1}, {x4, x1}, {x5,x2,x6} ... итд. ? И есть сомнения по поводу прочерков. Их действительно надо заменять, или оставить? Может ли x1 например быть соовместимым с самим собой? - кажется странным. Определение отношения совместимости нашел, но там для двух разных множеств. Спасибо! 0

Байт Диссидент 27706 / 17322 / 3812 Регистрация: 24.12.2010 Сообщений: 38,979
	05.11.2016, 10:02	9
	Сообщение от Hacker1995 И есть сомнения по поводу прочерков. Их действительно надо заменять, или оставить? Может ли x1 например быть соовместимым с самим собой? - кажется странным. Определение отношения совместимости нашел, но там для двух разных множеств. Признаюсь честно. Понятие "отношение (не-)совместимости" встречаю впервые. Сейчас слегка погуглил - да, есть такое в логике. Но я подошел к этому, как алгебраист. Вот, есть какое-то отношение (подмножество прямого квадрата базового множества). Видимо, оно же без приставки "не" обозначает его дополнениние. А в дополнение входит главная диагональ. Не нравится такой подход? И не надо. Не включайте. На дальнейшее это не должно оказать никакого действия. Сообщение от Hacker1995 это упорядоченные множества, или нет? То есть, надо ли находить еще и Нет. Не надо. Понятие множества само по себе не предполагает наличия на на нем порядка. Вот множество подмножеств, оно - да, на нем есть естественный порядок (не линейный). Потому-то вас и просят найти МАКСИМАЛЬНЫЕ совместимые подмножества. 2

Максимальные совместимые подмножества

Решение