Элементы дискретной математики. К. Д. Ушинского Элементы дискретной математики Ярославль, 2005 па. Корнилов, ни. Никулина, Семенова О. Г. Элементы дискретной математики. Учебное пособие
 Скачать 0.81 Mb.
|
|
n n n k n n n C C C C 2 1 0 = + + + + + 217. Чему равна сумма 7 5 7 3 7 1 7 C C С С + + + ? 218. Чему равна сумма 8 8 6 8 4 8 2 8 C C C C + + + ? 219. Докажите тождество m i m n m n m i i n C C C C − − ⋅ = ⋅ 220. Докажите тождество n m n m C n C m ⋅ = ⋅ − − 1 1 221. Получить все различные коэффициенты, которые будут появляться при приведении подобных членов в формулах (x+y+z) 6 и (x+y+z+u) 5 222. Найти коэффициенты при х после раскрытия скобок и приведения подобных членов в выражении (2+х 3 +х 4 ) 13 223. Найти коэффициенты при х после раскрытия скобок и приведения подобных членов в выражении (1+х 2 -х 3 ) 9 224. Найти коэффициенты при хи х после раскрытия скобок и приведения подобных членов в выражении (1+х 5 +х 7 ) 20 225. В каком из выражений (1+х 2 -х 3 ) 1000 , (1-х 2 +х 3 ) 1000 будет после раскрытия скобок и приведения подобных членов больший коэффициент при х 17 Рекуррентные соотношения. 226. Подсчитать количество последовательностей длины N, состоящих из 0 ив которых никакие две единицы не стоят рядом. Посылка бандероли стоит 18 рублей, а на почте имеются марки пои рублей. Сколькими разными способами можно наклеить на бандероль марки, на нужную сумму 61 228. Имеется возможность передавать 4 разных сигнала А, Б, В, Г, причем их передача занимает соответственно Т, Т Т, Т (целые) единиц времени. Сколько различных сообщений может быть передано за время Т (тоже целое 229. Абитуриент сдает в вуз 4 экзамена по балльной системе и хочет набрать не менее 17 баллов. Сколькими способами он может это сделать. 230. Сколькими способами можно разбить натуральное число М на К простых слагаемых, где способы разбиения, отличающиеся порядком слагаемых, считаются разными Например при Ми К ответом будет 3, так как 10=3+7=5+5=7+3. 231. В лототроне имеются бочонки с номерами от 1 до К. Последовательно вынимают по одному бочонку, записывают его номер и считают сумму записанных чисел. Сколькими способами может получиться сумма МВ лототроне имеются бочонки с номерами от 1 до К. Последовательно вынимают по одному бочонку, записывают его номер и считают сумму записанных чисел, после записывания номера бочонок возвращается обратно в лототрон. Сколькими способами может получиться сумма М 233. На единственной улице в деревне стоят К домов с известными координатами. Требуется соединить их телефонными проводами минимальной суммарной длины так, чтобы житель каждого дома мог пообщаться хотя бы с одним жителем другого дома. 234. В пригородном автобусе кондуктор следил затем, чтобы все покупали билеты и отмечал, сколько билетов (k i,j ) куплено с й остановки до й. По известной матрице k i,j нужно найти промежуток времени, когда в автобусе было максимальное количество пассажиров и чему оно равно. 235. Прямоугольная таблица размерами МхК произвольно заполнена цифрами от 0 до 9. Найти путь из левого нижнего угла в правый верхний с максимальной суммой цифр в клетках пути (разрешается на каждом шаге переходить вверх или вправо. 236. В романе N глав, причем р-я глава состоит из Ар страниц. Роман нужно разбить на К томов, причем главы должны идти по порядку и главы нельзя разбивать в разные тома. Какова может быть минимальная толщина самого толстого тома при этом 237. Для последовательности си, удовлетворяющей рекуррентному соотношению f(к+2)=5f(к+1)-6f(к), выписать формулу общего члена. 238. Для последовательности си, удовлетворяющей рекуррентному соотношению f(к+2)=6f(к+1)-9f(к), выписать формулу общего члена. 239. Для последовательности си, удовлетворяющей рекуррентному соотношению f(к+3)=-6f(к+2)-11f(k+1)-6f(к), выписать формулу общего члена. 240. Найдите общее решение рекуррентных соотношений 62 a) а n+2 -7a n+1 +12a n =0; b) а n+2 +3a n+1 -10a n =0; c) а n+2 +9a n =0 ; d) а n+2 +4a n+1 +4a n =0. 241. Найдите решение рекуррентного соотношения a) а n+2 -5a n+1 +6a n =0, а, а b) а n+2 -4a n+1 +4a n =0, а, а. Задачи по теории графов Основные определения и примеры графов. 1. В шахматном турнире по круговой системе участвуют семь студентов. Известно, что Ваня сыграл шесть партий, Толя – пять, Леша и Дима потри, Семени Илья – по две, Женя - одну. С кем сыграл Леша 2. Покажите, что следующие объекты можно рассматривать как графы · вершины и ребра многогранника · план лабиринта · дружеские отношения в группе студентов · генеалогическое дерево · теннисный турнир · страны на карте. 3. На рисунке изображены молекулы этилена и бензола через Си Н обозначены атомы углерода и водорода соответственно. Можно ли считать эти диаграммы графами Если да, то что будет являться необходимым условием, для того чтобы граф представлял собой молекулу какого-либо углеводорода 4. Могут ли степени вершины в простом графе быть равны • 8, 6, 5, 4, 4, 3, 2, 2; • 7, 7, 6, 5, 4, 2, 2, 1; • 6, 6, 6, 5, 5, 3, 2, 2. 5. Докажите, что число людей, когда-либо живших на Земле и сделавших нечетное число рукопожатий, четно. 6. В городе Маленьком 15 телефонов. Можно ли их соединить проводами так, чтобы каждый телефон был соединен ровно с пятью другими 7. Можно ли нарисовать на плоскости 9 отрезков так, чтобы каждый пересекался ровно стремя другими С Н Н Н НС С Н Н Н Н Н НС С С С С СВ городе Маленьком 15 телефонов. Можно ли их соединить проводами так, чтобы было 4 телефона, каждый из которых соединен стремя другими, 8 телефонов, каждый из которых соединен с шестью, и 3 телефона, каждый из которых соединен с пятью другими 9. В группе 30 человек. Может ли быть так, что 9 из них имеют подруга (в этой группе, 11 - подруга, а 10 - по 5 друзей 10. В некоторой стране 19 регионов. Может ли оказаться так, что у каждого региона 1, 5 или 9 соседних регионов 11. В государстве 100 городов, и из каждого из них выходит 4 дороги. Сколько всего дорог в государстве 12. Может ли в государстве, в котором из каждого города выходит 3 дороги, быть ровно 100 дорог 13. В розыгрыше первенства по футболу участвуют 20 команд. Какое наименьшее число игр должно быть сыграно, чтобы среди любых трех команд нашлись две, уже сыгравшие между собой 14. Нарисуйте полный граф с n вершинами, если а) n = 2 б) n = 3 в) n = 5 15. Какова степень каждой вершины полного графа, у которого n вершин 16. Спортивные соревнования проводятся по круговой системе. Это означает, что каждая пара игроков встречается между собой ровно один раз. В соревновании с двенадцатью участниками провели все встречи. Сколько было сыграно встреч 17. Может ли полный граф иметь 7, 8, 9, или 10 ребер 18. В некотором государстве система авиалиний устроена так, что любой город соединен авиалиниями не более чем стремя другими и из любого города в любой другой можно перелететь, сделав не боле одной пересадки. Какое наибольшее число городов может быть в этом государстве 19. Какие из предложенных графов являются регулярными 20. В некоторой компании любые два знакомых не имеют общих знакомых, а любые два незнакомых имеют ровно двух общих знакомых. Докажите, что в этой компании все имеют одинаковое число знакомых. 65 21. Известно, что в компании каждый человек знаком не менее, чем с половиной присутствующих. Докажите, что можно выбрать из компании четырех человек и рассадить их за круглым столом так, что при этом каждый будет сидеть рядом со своими знакомыми. 22. Спортивные соревнования проводятся по круговой системе. Это означает, что каждая пара игроков встречается между собой ровно один раз. Докажите, что в любой момент времени найдутся хотя бы два игрока, проведшие одинаковое число встреч. 23. Докажите, что в любом графе найдутся по крайней мере две вершины одинаковой степени 24. В футбольном турнире 20 команд сыграли 8 туров каждая команда сыграла с 8 разными командами. Докажите, что найдутся три команды, не сыгравшие между собой пока ни одного матча. 25. Про некоторую компанию известно, что каждый человек знаком в ней ровно с шестью людьми и для любой группы из шести человек найдется член компании, знакомый с каждым из этой шестерки. Сколько человек в компании 26. Докажите, что среди любых шести человек есть либо трое попарно знакомых, либо трое попарно незнакомых. 27. В международном фестивале участвовало несколько сотен делегатов из разных стран мира. Выяснилось, что из любых трех делегатов по крайней мере двое смогут объясниться между собой на каком-то языке. Докажите, что найдется тройка делегатов, в которой каждый может объясниться с каждым. Матрицы, ассоциированные с графом 28. Дана симметричная матрица размером n х n. В каждой строке расположено нечетное число единиц, остальные элементы равны нулю. Элементы на главной диагонали равны нулю. Доказать, что n является четным. 29. Опишите матрицы смежности полных графов, вполне несвязных графов. Что можно сказать о матрице простого графа и его дополнения 30. Изобразите матрицу смежности графа 31. Изобразите матрицу инцидентности графа. 66 32. Изобразите матрицы смежности, инцидентности графа 33. Дана матрица смежности. Изобразите граф, ей соответствующий. 1 2 3 4 5 6 7 1 0 0 1 1 0 1 0 2 0 0 0 0 1 0 1 3 1 0 0 1 0 1 0 4 1 0 1 0 1 0 1 5 0 1 0 1 0 0 1 6 1 0 1 0 0 0 0 7 0 1 0 1 1 0 0 34. Дана матрица инцидентности. Изобразите граф, ей соответствующий. 1 2 3 4 5 E1 1 0 0 0 1 E2 0 1 0 0 1 E3 0 0 0 1 1 E4 0 0 1 1 0 E5 0 0 1 0 1 E6 0 1 0 1 0 E7 1 0 1 0 0 35. Установить, какие из следующих матриц являются матрицами смежностей простого графа, какие - матрицами инциденций и какие не являются ни теми, ни другими. а) 0 0 1 0 1 0 1 0 0 0 1 0 1 1 1 0 0 1 1 0 0 0 1 1 0 0 1 1 1 0 1 0 0 0 1 0 1 0 1 0 0 1 1 1 0 1 1 1 0 б) 0 1 0 1 0 1 0 1 1 0 1 0 1 0 0 1 1 0 0 1 1 1 0 0 0 0 1 0 1 0 1 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 0 1 1 1 1 1 0 0 0 1 1 1 1 1 0 0 0 0 в) 1 1 1 1 0 0 1 0 0 0 0 0 0 1 0 0 1 1 0 0 1 0 1 0 0 0 0 1 0 г) 1 1 1 1 1 0 0 0 0 0 1 0 1 0 0 1 0 0 1 1 1 0 0 1 0 0 0 1 1 0 0 0 0 0 д) 1 0 0 1 0 1 0 1 1 1 0 1 0 1 0 0 0 0 0 0 0 1 0 1 0 1 0 0 е) 1 1 1 1 1 1 1 0 1 0 1 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 9 4 7 8 e9 e10 e2 e3 1 5 e1 e4 e8 e7 2 3 6 e11 e5 e6 Изоморфизм графов 36. Являются ли изоморфными графы Ответ обосновать. 37. Докажите, что графы являются изоморфными. 38. Докажите, что графы являются изоморфными. 39. Докажите, что графы не изоморфны. 40. Докажите, что графы не изоморфны. Достижимость и связность. 41. Дана матрица смежности графа. Не изображая граф, ответьте наследующие вопросы • Какова степень пятой вершины Назовите смежные с ней вершины. • Существует ли путь из вершины 2 в вершину 8? 1 2 3 4 5 6 7 8 1 0 1 1 0 0 0 0 0 2 1 0 0 0 0 0 0 0 3 1 0 0 1 0 0 0 1 4 0 0 1 0 0 0 0 0 5 0 0 0 0 0 1 1 0 6 0 0 0 0 1 0 1 0 7 0 0 0 0 1 1 0 0 8 0 0 1 0 0 0 0 0 42. Изобразите матрицу достижимости графа. 68 43. Дана матрица смежности графа. Найти все вершины, входящие в одну компоненту связности с вершиной 7. 1 2 3 4 5 6 7 8 9 10 1 0 1 1 0 0 0 0 0 0 0 2 1 0 1 0 0 0 0 0 0 0 3 1 1 0 0 0 0 0 0 0 0 4 0 0 0 0 1 0 1 0 0 0 5 0 0 0 1 0 1 0 0 0 0 6 0 0 0 0 1 0 1 0 0 0 7 0 0 0 1 0 1 0 0 0 0 8 0 0 0 0 0 0 0 0 1 1 9 0 0 0 0 0 0 0 1 0 1 10 0 0 0 0 0 0 0 1 1 0 44. Выделите компоненты связности графа (3 балла) 0 1 1 0 0 0 0 1 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 0 1 0 0 0 0 1 1 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 0 1 0 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 0 1 0 0 1 0 0 1 0 0 0 1 1 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0 0 45. Дана матрица смежности графа. Найдите матрицу достижимостей этого графа, не изображая его. 1 2 3 4 5 6 7 8 9 1 0 0 0 1 0 0 1 0 0 2 0 0 1 0 0 0 0 0 0 3 0 1 0 0 0 0 0 0 0 4 1 0 0 0 0 0 1 0 0 5 0 0 0 0 0 1 0 1 1 6 0 0 0 0 1 0 0 1 1 7 1 0 0 1 0 0 0 0 0 8 0 0 0 0 1 1 0 0 1 9 0 0 0 0 1 1 0 1 0 46. В стране Семерка 15 городов, каждый из которых соединен дорогами не менее чем с 7 другими. Докажите, что из любого города можно добраться до любого другого (возможно, проезжая через другие города. 47. Докажите, что граф с n вершинами, степень каждой из которых не менее (n–1)/2- связен. 48. В некотором государстве лишь один вид транспорта – автомобиль. Из столицы выходит 21 автомобильная дорога, из города Дальний - одна, а из всех остальных городов - по 20. Докажите, что из столицы можно доехать в Дальний (возможно, с пересадками. 69 49. В стране из каждого города выходит 100 дороги от любого города можно добраться до любого другого. Одну дорогу закрыли на ремонт. Докажите, что и теперь от любого города можно добраться до любого другого. 50. Докажите, что если в графе все вершины имеют четную степень, тов графе нет ребра, удаление которого приводит к увеличению количества компонент связности. 51. Водной стране каждая пара городов соединена только одним транспортным маршрутом или железнодорожным, или автобусным. Докажите, что существует вид транспорта, которым можно доехать из любого города страны в любой другой (возможно, с пересадками) 52. Докажите, что либо сам граф, либо дополнение к нему является связным. 53. На конференции по новым информационным технологиям студент Иванов познакомился с 52 студентами из разных городов России. По окончании конференции некоторые пары студентов обменялись адресами, причем у каждого из участников конференции оказалось не менее 26 адресов. Через некоторое время Иванову понадобилось узнать адрес студента Петрова, который также участвовал в конференции. Докажите, что Иванов может узнать адрес Петрова. 54. Каждый из семи мальчиков имеет не менее трех братьев. Докажите, что все мальчики – братья. 55. Докажите, что если выполняется соотношение q>(p-1)·(p-2)/2, где q – количество ребер, а p количество вершин, то граф связен. 56. Докажите, что если граф с q ребрами и p вершинами связен, то (p-1)<=q<=(p-1)·p/2. 57. На рисунке изображен граф. Найдите • ребра графа, являющиеся мостами • точки сочленения графа • двусвязные компоненты. 58. Докажите, что ребро в графе является мостом тогда и только тогда, когда оно не содержится нив одном из циклов. 59. На озере 7 островов (1 – 7), которые соединены мостами 1 сиси сиси сиси си Определить, можно лис любого острова добраться на любой и существует ли мост, при уничтожении которого это сообщение между островами нарушается. Циклы 60. На рисунке изображена карта Кенигсбергских мостов. Определите, можно ли, начав с некоторой точки, совершить прогулку и вернуться в исходную точку, пройдя по каждому мосту ровно 1 раз. 61. Имеется группа островов, соединенных мостами так, что от каждого острова можно добраться до любого другого. Турист обошел все острова, пройдя по каждому мосту ровно один раз. На острове Троекратном он побывал трижды. Сколько мостов ведет с Троекратного, если туриста) нес него начали не на нем закончил б) с него начал, ноне на нем закончил в) с него начали на нем закончил 62. Определите, является ли граф, заданный матрице смежности, эйлеровым. (1 балл) 0 1 1 1 1 1 1 1 0 1 0 0 0 0 1 1 0 1 1 0 0 1 0 1 0 0 0 0 1 0 1 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 1 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 1 1 0 0 1 1 0 0 0 0 1 1 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 1 0 1 0 0 1 0 0 0 0 1 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 63. Существует ли эйлеров граф, обладающий висячей вершиной 64. Привести пример графа, все степени которого четны, но который не является эйлеровым. 65. Для каких графов можно найти цикл, проходящий по каждому ребру 1 раз 66. Для каких графов можно найти маршрут, проходящий по каждому ребру 1 раз 67. Докажите, что на любом связном графе с 2k нечетными вершинами можно указать семейство из k маршрутов, которые в совокупности содержат все ребра графа по одному разу. 68. Имеется полный граф на 16 вершинах. Каково минимальное число маршрутов в графе, которые в совокупности содержат все его ребра и все вершины 69. Дан кусок проволоки длиной 120 см. а) Можно лине ломая проволоки, изготовить каркас куба с ребром 10 см б) Какое наименьшее число раз придется ломать проволоку, чтобы все же изготовить требуемый каркас 70. Можно ли нарисовать решетку, изображенную на рисунке, не отрывая карандаш от бумаги и не проводя одну и туже линию дважды Какое наименьшее число раз придется оторвать карандаш от бумаги А В D С 71 71. На плоскости дано 100 окружностей, составляющих связную (то есть не распадающуюся на части) фигуру. Докажите, что эту фигуру можно нарисовать, не отрывая карандаша от бумаги и не проводя дважды одну и туже линию. 72. Для каких чисел m, n граф G является эйлеровым: 1) К – полный граф с n вершинами 2) K mn – полный двудольный граф с n, m вершинами 3) W n – колесо с n вершинами 73. Для каких чисел m, n граф является гамильтовым? 1) К – полный граф с n вершинами 2) W n – колесо с n вершинами 74. Дана матрица смежности графа. Определить, является ли граф эйлеровым, гамильтоновым. 1 2 3 4 5 1 0 1 0 1 1 2 1 0 1 1 1 3 0 1 0 1 1 4 1 1 1 0 1 5 1 1 1 1 0 75. В стране некоторые пары городов соединены авиалиниями, причем каждый город соединен не менее чем с половиной других городов. Докажите, что туристическая фирма может найти такой маршрут облета городов, который начинается и заканчивается водном и том же городе, причем каждый город посещает ровно один раз. 76. На пир при дворе короля Артура собралось четное число рыцарей, которые либо враждуют, либо дружат. Оказалось, что у каждого рыцаря друзей больше, чем врагов. Докажите, что можно рассадить рыцарей за круглым столом таким образом, что справа и слева от каждого из них будет сидеть друг. |