ВУЗ:
Составители:
Рубрика:
СПИСОК ЛИТЕРАТУРЫ
1 Басакер Р., Саати Т. Конечные графы и сети. Пер. с англ. М.: Наука, 1973. 368 с. (Гл. 3, 6 – 9).
2 Бауэр Ф. Л., Гооз Г. Информатика. Вводный курс: В 2 ч. Пер. с нем. М.: Мир, 1990. Ч. 2. 423 с.
(Гл. 1, 3).
3 Белов В. В., Воробьев Е. М., Шаталов В. Е. Теория графов: Учеб. пособие для втузов. М.: Выс-
шая школа, 1976. 392 с. (Гл. 1 – 3, 6 – 9).
4 Гаврилов Г. П., Сапоженко А. А. Сборник задач по дискретной математике. М.: Наука, 1977. 368
с. (Гл. 4, 5, 7, 9, 10).
5 Горбатов В. А. Основы дискретной математики: Учеб. пособие для студентов вузов. М.: Высшая
школа, 1986. 311 с. (Гл. 1 – 10).
6 Кузнецов О. П., Адельсон-Вельский Г. М. Дискретная математика для инженера. М.: Энерго-
атомиздат, 1988. 480 с. (Гл. 1 – 5, 8, 10).
7 Новиков Ф. А. Дискретная математика для программистов. СПб.: Питер, 2004. 302 с. (Гл. 1 – 9).
8 Оре О. Графы и их применение. Пер. с англ. М.: Мир, 1965. 174 с. (Гл. 3, 6 – 9).
9 Уилсон Р. Введение в теорию графов. Пер. с англ. М.: Мир, 1977. 208 с. (Гл. 6, 8, 9).
10 Харари Ф. Теория графов. Пер. с англ. М.: Мир, 1973. 301 с.
(Гл. 3, 6, 7, 8, 9).
Задачи к теме «Отношения. Способы задания и свойства. Понятие модели»
16 Представить перечислением элементов квадрат множества М: а) М={1, 2}; б) М={a, b, c}; в)
М={3, 4}; г) М={d, e, f}.
17 Представить с помощью матрицы смежности бинарное отношение Т в множестве M={a, b, c, d},
заданное перечислением элементов: а) Т={(a, a), (a, b), (b, b), (b, c), (c, a), (d, d)}; б) Т={(a, c), (b, a), (b,
d), (c, c), (c, d)}; в) Т={(a, b), (b, a), (b, d), (c, a), (d, b), (d, c)}; г) Т={(a, d), (b, c), (c, b), (c, c), (d, a), (d, d)}.
18 Представить перечислением элементов бинарное отношение Т в множестве М={1, 2, 3, 4}, за-
данное с помощью графа:
19 Представить с помощью фактор-множества M/T бинарное отношение Т в множестве M={a, b, c},
заданное перечислением элементов: а) Т={(a, a), (b, b), (b, c), (c, a)}; б) Т={(b, a), (c, a), (c, b), (c, c)}; в)
Т={(a, a), (a, c), (b, a), (b, b) }; г) Т={(a, a), (a, b), (a, c), (c, c)}.
20 Установить, является ли рефлексивным, антирефлексивным или нерефлексивным бинарное от-
ношение Т в множестве М={1, 2, 3, 4}: а) Т={(1, 1), (2, 3), (4, 2), (4, 1), (4, 4)}; б) Т={(1, 1), (1, 2), (2, 2),
(3, 3), (4, 4)}; в) Т={(1, 2), (3, 1), (3, 2), (3, 4), (4, 2)}; г) Т={(1, 1), (1, 4), (2, 2), (3, 2), (3, 3), (4, 4)}.
21 Установить, является ли симметричным, антисимметричным или несимметричным бинарное
отношение Т в множестве M={a, b, c, d}: а) Т={(a, a), (b, c), (b, d), (c, b), (d, b)}; б) Т={(a, b), (b, a), (b, b),
(b, c), (d, b)}; в) Т={(a, b), (b, a), (b, c), (c, d), (d, c)}; г) Т={(b, a), (b, c), (c, a), (c, c), (d, a)}.
22 Установить, является ли транзитивным, антитранзитивным или нетранзитивным бинарное от-
ношение Т в множестве М={1, 2, 3, 4}: а) Т={(1, 1), (1, 2), (2, 4), (4, 3)}; б) Т={(1, 2), (3, 1), (3, 2), (4, 4)};
в) Т={(1, 2), (3, 1), (3, 2), (3, 4), (4, 2)}; г) Т={(1, 3), (2, 1), (2, 3), (3, 4)}.
23 Задать с помощью графа бинарное отношение в множестве M={a, b, c, d}, являющееся одновре-
менно: а) рефлексивным, симметричным и нетранзитивным; б) антирефлексивным, антисимметричным
и транзитивным; в) нерефлексивным, симметричным и антитранзитивным; г) рефлексивным, антисим-
метричным и антитранзитивным; д) антирефлексивным, несимметричным и нетранзитивным; е) нереф-
лексивным, несимметричным и транзитивным; ж) нерефлексивным, симметричным и транзитивным; з)
рефлексивным, несимметричным и нетранзитивным.
24 Определить, является ли заданное в множестве М={1, 2, 3, 4} бинарное отношение Т бинарным
отношением упорядоченности ≤: а) Т={(1, 1), (1, 2), (2, 2), (3, 1), (3, 2), (3, 3), (4, 4)}; б) Т={(1, 1), (1, 4),
(2, 2), (3, 1), (3, 4), (4, 2), (4, 4)}; в) Т={(1, 1), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 3), (4, 4)}; г) Т={(1, 1), (1,
3), (2, 1), (2, 2), (2, 3), (2, 4), (3, 3), (4, 3), (4, 4)}; д) Т={(1, 1), (2, 2), (2, 4), (3, 2), (3, 3), (4, 1), (4, 4)}; е)
Т={(1, 1), (1, 3), (2, 2), (2, 4), (3, 1), (3, 3), (4, 2), (4, 4)}; ж) Т={(1, 1), (1, 2), (2, 2), (3, 1), (3, 2), (3, 3), (3, 4),
(4, 4)}; з) Т={(1, 1), (1, 2), (1, 4), (2, 2), (3, 1), (3, 2), (3, 3), (3, 4), (4, 2), (4, 4)}.
1
3
2
4
а)
1
3
2
4
б)
1
3
2
4
в)
1
3
2
4
г)
