Требование к зачету по дисциплине
«Дискретная математика».
Группа МК-301
2014-2015 учебный год.
Для зачета необходимо решить и сдать две контрольные работы.
Домашняя контрольная работа по комбинаторике
Во всех заданиях параметры a, b, c, d, e и f обозначают соответственно число букв в вашем имени,
отчестве и фамилии, число, месяц и год вашего рождения.
1. Сколькими способами можно расставить на шахматной доске размера a × a a ладей, так чтобы
они били все поля?
2. Сколькими способами можно расставить на шахматной доске размера a × a a ладей, так чтобы
они не били друг друга?
3. Сколькими способами можно рассадить за b + c парт b + c мальчиков и b + c девочек, так чтобы
за каждой партой сидели мальчик и девочка?
4. Сколькими способами можно рассадить за 2c парт 2c мальчиков и 2c девочек, так чтобы за каждой
партой сидели двое детей одного пола?
5. Сколько существует перестановок цифр {0, 1, . . . , 9}, таких что за цифрой 0 идет цифра 1?
6. Сколько существует перестановок цифр {0, 1, . . . , 9}, таких что цифра 0 стоит левее цифры 1?
7. Найти число подмножеств X множества {0, 1, . . . , a + b + c}, состоящих из a четных и b нечетных
чисел.
8. Найти число подмножеств X множества {0, 1, . . . , a + b + c}, таких что |X| ≤
a+b+c+1
.
2
9. На окружности отмечено a + b + c точек A1 , . . . , Aa+b+c . Сколько существует треугольников с
вершинами в отмеченных точках, не имеющих общих точек с прямой Aa Ac ?
10. Сколькими способами можно разложить a белых и b черных шаров по c различным ящикам?
11. Дан квадрат, каждая его сторона разбита на c частей, через эти точки проведены линии параллельные сторонам. Сколько существует прямоугольников, ограниченных проведенными линиями?
12. Найти коэффициент при xb в разложении многочлена (x2 + ax − c)b .
13. Сколько есть чисел не превосходящих f + e и не делящихся ни на одно из чисел a, b, c, d + e?
14. Сколькими способами можно расставить на шахматной доске размера a × a a ладей, так чтобы
они не били друг друга и ни одна не стояла на главной диагонали?
15. Случайным образом выбирается перестановка на множестве 0, 1, . . . , c. ξ — случайная величина
равная количеству элементов, остающихся на своих местах. Найти математическое ожидание и
дисперсию случайной величины ξ.
16. Сколько существует двоичных последовательностей длины b, не содержащих двух единиц подряд?
17. Рассмотрим множество путей на прямой состоящих из шагов на 1 влево или вправо. Найдите
рекуррентное соотношение и производящую функцию числа таких путей начинающихся в 0 и
оканчивающихся в точке a.
18. Найти производящую функцию последовательности an = (n + a)(n + b).
19. Найти общий член последовательности, для которой функция F (t) = (t + . . . + ta )b является производящей.
1
Домашняя контрольная работа по теории
графов
Во всех заданиях параметры a, b, c, d, e и f обозначают соответственно число букв в вашем имени, отчестве и фамилии, число,
месяц и год вашего рождения.
1. Пусть Gn — граф с множеством вершин {6, 7, . . . , n} и вершины
i и j смежны тогда и только тогда, когда i и j взаимнопросты.
Постройте граф Gb+c , выпишите его матрицу смежности.
2. Постройте все графы на b вершинах регулярные степени b − 3.
3. Самодополнительным графом называется граф изоморфный
своему дополнению. Приведите пример самодополнительного
графа на 4a вершинах.
4. Найдите остовное дерево графа Gb+c (из первой задачи), постройте фундаментальные системы циклов и разрезов ассоциированные с этим деревом. Найдите циклический и коциклический ранг графа.
5. Найдите хроматические числа платоновых графов (графы правильных многогранников).
6. Найдите хроматическое число графа Gb+c , по любому из двух
алгоритмов.
7. Найдите гамильтонов цикл в графе Gb+c , по методу Флореса и
Робертса.
8. Решите на графе Gb+c задачу китайского почтальона с весами
всех ребер равными 1.
9. Найдите минимальное покрытие множества вершин графа Gb+c
окрестностями его вершин.
10. Найдите хроматический многочлен октаэдра.
11. По алгоритму Брона-Кэрбоша найдите все независимые множества куба.
12. Найдите хроматический многочлен графа Ca .
1
13. Турнир называется транзитивным, если из существования дуг
(u, v) и (v, w), следует существование дуги (u, w). Докажите,
что транзитивный турнир не является сильно связным.
14. Какое максимальное и минимальное число ребер может быть в
графе с d + e + c вершинами и a компонентами связности.
15. Среди a + c человек, каждый знаком не менее чем с c другими.
Докажите, что найдутся три человека знакомые друг с другом.
16. Несколько авиакомпаний решили связать авиалиниями (b + c) ∗
(d + e) городов так, чтобы выполнялось два условия: 1) любые
два города были соединены линией не более чем одной компании. 2) любая компания, пользуясь только своими линиями,
могла бы доставить пассажира из любого города в любой другой. При каком наибольшем числе компаний это возможно.
17. В стране a + b городов, каждый соединен авиалиниями с c другими. Можно ли гарантировано (то есть независимо от конкретного расположения линий) совершить перелет по всем городам,
с концоми началом в одном городе и посетив каждый город по
одному разу.
18. Имеется d домов и a колодцев каждый хозяин дома пользуется
всеми колодцами. Однажды хозяева поссорились. Можно ли
проложить дорожки так, чтобы они не пересекались.
19. Найдите соотношение для числа вершин и граней плоского графа, если каждая грань ограничена не менее чем a − 1 ребром.
20. c часовых лекций занумерованы числами от 2 до c + 1, две
лекции могут читаться одновременно если соответствующие им
числа взаимно просты. За какое наименьшее время могут быть
прочитаны все эти лекции.
21. a часовых лекций занумерованы числами от 2 до a + 1, две
лекции не могут читаться одновременно если соответствующие
им числа взаимно просты. Всего есть b часов для возможного
чтения этих лекций. Сколькими способами можно составить
расписание.
22. В компании любые двое знакомых не имеют общих знакомых.
А любые двое незнакомых имеют ровно 2-х общих знакомых.
Докажите, что все имеют одинаковое число знакомых.
2
1/--страниц