Рассмотрим множество M состоящего из всех непустых подмножеств А,В,... множества {1,2,3,4,5}. На множестве M введено отношение R: A R B <=> |A(операция переcечения) B| =1

  1. Сколько элементов имеет множество М?
  2. Перечислите свойства отношения R
  3. Сколько единиц имеет матрица R?
  4. Сколько ребер включая петли, имеет граф транзитивного замыкания
    R?

задан 19 Июн '17 0:35

изменен 19 Июн '17 0:55

Тут тоже надо бы внести исправления.

С пунктами не возникает проблемы, если их номера писать со скобкой. Типа 1), 2) и т.п.

(19 Июн '17 0:50) falcao
10|600 символов нужно символов осталось
0

1) Подмножеств здесь всего 2^5, из них одно пустое. Значит, M состоит из 31 элемента.

2) Плохо, когда задачу формулируют в таком виде, хотя это происходит весьма часто. Ведь из общих соображений понятно, что любой объект обладает (или не обладает) бесконечным набором свойств. Здесь приходится догадываться, что свойства берутся из готового списка -- типа, рефлексивность, симметричность, транзитивность. Надо ли при этом учитывать антирефлексивность и прочее? Раз не сказано, то я не буду.

Рефлексивности, очевидно, нет, так как пересечение A с A не обязано быть одноэлементным. Симметричность очевидна в силу симметричности операции пересечения. Транзитивности нет, и можно привести контрпример. Берём A={1,2}, B={2,3}, C={3,4}. Тогда A R B, B R C верны (пересечения одноэлементны), но A R C неверно (пересечение пустое).

3) Здесь нужно найти число упорядоченных пар непустых подмножеств (A,B), пересечение которых одноэлементно. Пусть |A|=k -- число от 1 до 5. Посмотрим, сколько подмножеств B подходит для A. Общий элемент можно загадать k способами. Остальные элементы B образуют подмножество дополнения A, и их будет 2^{5-k}. Значит, каждое множество A мощности k даёт нам k2^{5-k} вариантов. Подмножеств такой мощности имеется C_5^k. Домножаем на число сочетаний и суммируем по k=1,...,5. Числа тут не очень большие, и проще всего сделать прямой подсчёт. Он даёт 405. При желании, это же число можно получить при помощи биномиальных тождеств.

4) Легко проверить, что транзитивное замыкание является полным отношением на M. Это значит, что от любого непустого подмножества можно перейти к любому непустому при помощи "цепочки", где соседние элементы имеют одноэлементное пересечение. Достаточно убедиться в том, что от любого подмножества из M можно этим способом перейти к {1}. Если 1 принадлежит M, это делается за один шаг. Если нет, то берём любой элемент из M (оно непусто), и пусть это x. Формируем множество {1,x}, а от него переходим к {1}. Итого граф будет иметь 31^2=961 ориентированное ребро, включая петли.

ссылка

отвечен 19 Июн '17 1:34

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,477
×627
×552

задан
19 Июн '17 0:35

показан
624 раза

обновлен
19 Июн '17 1:34

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru