Требование к зачету по дисциплине «Дискретная математика». Группа МК-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/--страниц