Элементы дискретной математики. К. Д. Ушинского Элементы дискретной математики Ярославль, 2005 па. Корнилов, ни. Никулина, Семенова О. Г. Элементы дискретной математики. Учебное пособие
 Скачать 0.81 Mb.
|
|
153. Перевозчику нужно переправить через реку волка, козу и мешок с капустой. Лодка так мала, что кроме перевозчика вне можно взять только один из объектов. Кроме того, капусту нельзя оставлять вместе с козой, а козу вместе с волком. Как осуществить переправу 154. В двадцатиэтажном доме испорчен лифт он может либо подниматься на 8 этажей вверх, либо спускаться на 13 этажей вниз. Можно лис помощью лифта попасть с 20 этажа на первый Когда сверху меньше 8 этажей, то лифт вверх не поедет. Аналогично, вниз) 155. Есть 3 бидона вместимостью 14 литров, 9 литров и 5 литров. В большем – 14 литров молока. Остальные пусты. Как с помощью этих сосудов разлить молоко поровну 156. Имеется четыре бочки. В первую входит 24 ведра, вместимость второй 13 ведер, третьей - 11 ведер, четвертой – 5 ведер. Вначале наполнена только первая бочка. Требуется её содержимое разлить натри равные части так, чтобы первые три бочки содержали по 8 ведер, а четвертая осталась пустой. 157. Три солдата и три разбойника должны переправиться через реку. Они нашли лодку, в которую помещаются только два человека. Нельзя оставить на берегу больше разбойников, чем солдат. Разрешается оставлять на берегу одних разбойников или одних солдат. Как всем шестерым переправиться через реку Найти всевозможные способы. 158. На столе лежит 15 спичек. Два игрока по очереди берут от одной до трех спичек. Проигрывает тот игрок, который взял последнюю спичку. Описать выигрышную стратегию. 159. Двое называют по очереди числа, меньшие 100. Начинают с нуля. Каждое новое число должно на 1, 2 или 3 увеличивать одну из цифр предыдущего числа. Проигрывает тот, кто вынужден назвать число 99. Описать выигрышную стратегию в двух случаях. 160. Играют двое. Первый игрок сообщает какую-нибудь дату января 1991 года. Каждый игрок на своем ходе называет более позднюю дату, увеличивая либо календарную дату в месяце, либо месяц, ноне то и другое сразу. Описать выигрышную стратегию, при которой a) игрок, назвавший 31 декабря, выигрывает b) игрок, назвавший 31 декабря, проигрывает. Плоские графы 161. Проверить формулу Эйлера для графов W 6 и К n 162. Для шахматной доски размером К х К найдите числа p, q, r и убедитесь в справедливости теоремы Эйлера. 163. Обобщите формулу Эйлера для несвязных графов. 164. В стране Озерная 7 озер, соединенных между собой 10 каналами, причем от любого озера можно доплыть до любого другого. Сколько в этой стране островов 165. Мэрия решила построить в каждом квартале города, имеющего 155 перекрестков и 260 отрезков улиц между перекрестками, универсам. Сколько будет построено универсамов 166. Докажите, что, если в планарном графе каждая грань есть С цикл длины n), q=n*(p- 2)/(n-2). 167. В квадрате отметили 20 точек и соединили их непересекающимися отрезками друг с другом и с вершинами квадрата так, что квадрат разбился на треугольники. Сколько получилось треугольников 168. Печатная плата представляет собой пластинку из изолирующего материала, в специально изготовленные гнезда которой устанавливают электронные приборы. В качестве проводников, соединяющих эти приборы, служат напыленные металлические дорожки. Поскольку проводники не изолируются, то дорожки не должны пересекаться. Если это может произойти, то одну из дорожек переносят на другую сторону платы. Конструктор Иванов придумал схему печатной платы, которая состоит из 12 приборов и 32 проводников, соединяющих их. Можно ли изготовить такую плату так, что все проводники будут расположены на одной её стороне 169. Докажите, что для плоского связного графа справедливо неравенство q<=3p-6 170. Докажите, что граф, имеющий 5 вершин, каждая из которых соединена ребром с любой другой, не является плоским. 171. Можно ли построить три дома, вырыть три колодца и соединить тропинками каждый дом с каждым колодцем так, чтобы тропинки не пересекались 172. Докажите, что для любого плоского графа (в том числе и несвязного) справедливо неравенство q<=3p-6. 173. Докажите, что граф, имеющий 10 вершин, степень каждой из которых равна 5, - неплоский. В графе степень любой вершины не меньше шести. Доказать, что его нельзя нарисовать на плоскости, так чтобы никакие два ребра его не пересекались. 83 175. Каждое ребро полного графа с 11 вершинами покрашено в один из двух цветов красный или синий. Докажите, что либо красный, либо синий граф не является плоским. 176. Покажите, что граф W 6 стягиваем к графу К 177. Докажите, что граф Петерсона не является планарным. 178. Инженер Иванов усовершенствовал свою плату. Теперь она имеет 9 приборов и 17 проводников. Схема платы представлена на рисунке. Можно ли изготовить такую плату так, что все проводники будут расположены на одной её стороне 179. Инженер Иванов придумал схему печатной суперплаты, которая может заменить целый компьютер. Плата состоит из 200 приборов и 2000 проводников. Ясно, что для реализации такой схемы нужно будет использовать многослойную плату, на которой проводники будут располагаться в разных слоях. Докажите, что разработанную схему нельзя изготовить в виде трехслойной платы. Стереографическая проекция 180. Докажите, что число вершин (p), ребер (q) и граней (r) любого выпуклого многогранника связано формулой p–q+r=2. 181. Доказать, что граф правильного многогранника является плоскими правильным. 182. Найти гамильтоновы циклы на правильных графах. 183. При изготовлении некоторой однослойной печатной платы по технологическим условиям один заданный проводник должен находится на краю платы. Доказать, что это всегда можно сделать. 184. Нарисуйте граф, изоморфный графу, изображенному на рисунке, так, чтобы внешней стала грань · 2 · 3 Двойственные графы 185. Найдите двойственные графы для следующих графов 84 186. Покажите, что граф, двойственный к колесу W n , является колесом. 187. Плоский граф G имеет 7 вершин, 10 ребер и 5 граней. Сколько вершин, ребер и граней имеет двойственный к нему граф. 188. Докажите, что у выпуклого многогранника найдутся две грани с одинаковым числом ребер. 189. Докажите, что не существует выпуклого многогранника, у которого все грани шестиугольники. 190. Может ли существовать плоский граф с пятью гранями, в котором каждая пара граней является смежными 191. Дан плоский граф, в каждой вершине которого сходится не более трех ребер. Докажите, что · четное число граней имеет нечетное число смежных граней · существует грань, которая имеет не более пяти смежных с ней граней. Раскраски графа 192. Найдите хроматические числа для · вполне несвязного графа с n вершинами · полного графа с n вершинами · двудольного графа, доли которого имеют n и m вершин · дерева с n вершинами. 193. Для графов, изображенных на рисунке, найдите хроматические числа и какую-либо правильную раскраску. 194. Сколькими способами можно раскрасить полный помеченный граф на 6 вершинах шестью цветами (Два способа считаются различными, если некоторая вершина при одном способе имеет один цвета при другом способе – другой) 195. Определите хроматические числа для графов платоновых тел 1 2 3 4 5 6 7 8 85 196. Граф называется критическим, если удаление любой его вершины вместе с инцидентными ей ребрами приводит к графу с меньшим хроматическим числом. Покажите, что К, является критическим графом при n >1. 197. Докажите, что всякий критический граф, являющийся хроматическим · связен · не имеет точек сочленения · степень каждой его вершины не меньше, чем k–1. 198. Коробка скоростей – механизм для изменения частоты вращения ведомого вала при неизменной частоте вращения ведущего. Это изменение происходит за счет того, что находящиеся внутри коробки шестерни вводятся в зацепление специальным образом. Одна из задач, стоящих перед конструктором коробки, заключается в минимизации числа валов, на которых размещаются шестерни. Некоторые шестерни не должны находиться на одном валу, например, они могут быть в зацеплении или их общий вес велик для одного вала, и т.д. В таблице крестиками указаны такие пары шестерен. Найдите минимальное число валов, на которые можно поместить шестерни. 1 2 3 4 5 6 7 1 + + + + 2 + + + + 3 + + + 4 + + 5 + + + + 6 + + + 7 + + + + 199. Образовавшийся коммерческий университет арендует здание для проведения занятий. В четверг проводится 7 лекций право, английский язык, французский язык, экономика, менеджмент, маркетинг, этикет. Чтение каждой лекции в отдельности занимает один час, но некоторые лекции не могут читаться одновременно. В таблице крестиком помечены лекции, которые не могут читаться одновременно. Определите минимальное время, за которое могут быть прочитаны лекции в четверг. тетраэдр куб октаэдр додекаэдр ПАФ Э ММ Э Право + + + Англ. яз. + + + + Фран. яз. + + + + Экономика + + + Менеджмент + + + + Маркетинг + + + + Этикет + + 200. Задача распределения оборудования. Заданы множество работ и механизмов. Для выполнения каждой из работ требуются некоторое время, одинаковое для всех работ, и некоторые механизмы. При этом ни один из механизмов не может быть одновременно занят в нескольких работах. Нужно распределить механизмы так, чтобы общее время выполнения всех работ было минимально. 201. Все страны, расположенные на острове, имеют форму треугольников, причем любые две граничащие страны имеют целую общую сторону (то есть вершина одного треугольника не может лежать на стороне другого. Докажите, что для раскраски карты этого острова так, чтобы никакие две соседние страны небыли окрашены в один цвет, достаточно трех красок. 202. Известно, что на карте некоторой области нет точек, в которых сходятся границы нечетного числа районов. Докажите, что такую карту можно раскрасить двумя цветами так, что любые два соседних района будут покрашены разными красками. 203. Докажите, что для раскраски карты, полученной при пересечении прямых и окружностей на плоскости, достаточно двух цветов. Список рекомендуемой литературы по теории графов № Тема Литература 1. Основные определения и примеры графов. 1 (гл. 1 § 1); 5 (гл. 1); 6 (гл. 6 § 1); 7 (гл. 1); 8 (гл. 1 § 2); 10 (гл. 7 § 1); 1 гл. 4 § 1); 12 (гл. 1 § 1, гл. 2 § 2, 3) 2. Изоморфизм графов. 5 (гл. 1 § 1); 10 (гл. 7 § 1); 12 (гл. 1 § 1, гл. 2 § 2) 3. Способы описания графов. 1 гл. 1 § 4); 2 (гл. 7 § 1); 5 (гл. 1 § 6); 6 (гл. 6 § 2); 7 (гл. 1 § 8); 10 (гл. 7 § 4); 11 (гл. 4 § 1) 4. Достижимость и связность. 1 гл. 1 § 2); 5 (гл. 5 § 33); 6 (гл. 6 § 5, 6); гл. 2);10 (гл. 8 § 1); 11 (гл. 4 § 3) 5. Мосты, блоки, меры связности. 1 (гл. 2 § 2, гл. 8 § 2); 2 (гл. . 7 § 4); 5 (гл. 5 § 34); 6 (гл. 6 § 13); 10( гл. 7 § 2) 6. Кратчайшие пути 1 гл. 10); 2 (гл. 6 § 3, 4); 5 (гл. 12 § 76); 6 (гл. 6 § 9); 7 гл. 8); 8 (гл. 3); 10 (гл. 8 § 7); 11 (гл. 4 § 5) 7. Обходы графа. 1 гл. 8 § 1, 4); 2 (гл. 7 § 3); 6 (гл. 6 § 3); 11 (гл. 4 § 9); 8. Эйлеровы циклы в графах. 1 (гл. 3 § 1, гл. 8 § 5); 5 (гл. 7 § 43); 6 (гл. 6 § 7); 10 (гл. 10 § 2); 12 (гл. 3 § 6) 9. Гамильтонов цикл на графе (гл. 3 § 2); 5 (гл. 7 § 44); 7 (гл. 10 § 2);10 (гл. 10 § 3); 12 гл. 3 § 7) 10. Задача коммивояжера 1 гл. 13); 7 (гл. 10 § 5, 6, 7); 8 (гл. 7) 11. Фундаментальные циклы и разрезы 6 (гл. 6 § 12); 10 (гл. 10 § 1); 11 (гл. 4 § 11, 12); 12. Деревья. Эквивалентные определения деревьев 1 (гл. 2 § 1); 5 (гл. 2 § 13); 7 (гл. 7 § 1);10 (гл. 9 § 1); 12 гл. 4 § 9) 13. Каркас минимального веса 2 (гл. 7 § 2); 5 (гл. 2 § 15, гл. 12 § 75); 6 (гл. 6 § 8); 7 (гл. 7 § 3);10 (гл. 9 § 5) 14. Двудольные графы. 6 гл. 6 § 14); 10 (гл 7 § 3.2) 15. Совершенное паросочетание и теорема Холла 5 (гл. 12 § 77); 7 (гл. 12); 10 (гл. 8 § 4); 12 (гл. 8 § 25) 16. Теорема Менгера 5 гл. 5 § 35); 10 (гл. 8 § 3); 12 (гл. 8 § 28) 17. Максимальное паросочетание 2 (гл. 7 § 5); 5 (гл. 12 § 77); 7 (гл. 12);8 (гл. 5) 18. Потоки в сетях 1 (гл. 11); 6 (гл. 6 § 10); 7 (гл. 11); 8 (гл. 4); 10 (гл. 8 § 5); 12 (гл. 8 § 29) 88 19. Независимые и доминирующие множества 5 (гл. 4); 6 (гл. 6 § 11); 7 (гл. гл. 11) 20. Ориентированный граф 1 гл. 1 § 3); 2 (гл. 6 § 1, 2); 5 (гл. 10 § 63, 64, 65); 12 (гл. 7 § 22) 21. Достижимость, связность в орграфах 1 (гл. 8 § 3); 2 (гл. 6 § 7); 7 (гл. 2);10 (гл. 8 § 6) 22. Эйлеров цикл в орграфах. 12 гл. 7 § 23) 23. Гамильтонов путь и цикл в орграфах. 12 (гл. 7 § 23) 24. Плоские графы. Планарность. 1 (гл. 5 § 1); 5 (гл. 6 § 36); 10 (гл. 12 § 2); 11 (гл. 4 § 15); 12 (гл. 5 § 12) 25. Укладки графов 1 гл. 5 § 11); 5 (гл. 6 § 41); 12 (гл. 2 § 4, гл. 5 § 14) 26. Формула Эйлера для плоских графов 1 (гл. 5 § 2); 5 (гл. 6 § 37); 12 (гл. 5 § 13) 27. Стереографическая проекция. гл. 6 §36); гл. 2 §4) 28. Двойственный граф 1 (гл. 5 § 4), 12 (гл. 5 § 15) 29. Раскраски графов 1 гл. 6 ); 5 (гл. 9); 10 (гл. 12 § 3); 11 (гл. 4 § 14); 12 (гл. 6) 30. Раскрашивание карт. Теорема о пяти красках. 10 (гл. 12 § 2.3); 12 (гл. 6) Список литературы 1. Асанов М. О, Баранский В. А, Расин В.В. Дискретная математика графы, матроиды, алгоритмы. – Ижевск, 2001. 2. Ахо А, Хокпкрофт Дж, Ульман Дж.Структуры данных и алгоритмы. – М Издательский дом «Вильямс», 2001. 3. Бадин НМ, Волченков С.Г., Дашниц Н.Л., Корнилов ПА. Ярославские олимпиады по информатике. – Ярославль, 1995. 4. Виленкин Н.Я. Комбинаторика. – М Наука, 1969. 5. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. – М Наука, 1990. 6. Иванов Б.Н. Дискретная математика. Алгоритмы и программы. – М Лаборатория базовых знаний, 2002. 7. Кристофидес Н. Теория графов. Алгоритмический подход. – М Мир, 1978. 8. Майника Э. Алгоритмы оптимизации на сетях и графах. – М.:Мир,1981. 9. Мельников О.И. Занимательные задачи по теории графов. – Минск Тетрасистемс, 2001. 10. Новиков ФА. Дискретная математика для программистов. – СПб.:Питер, 2001. 11. Судоплатов СВ, Овчинникова Е.В. Элементы дискретной математики. – М ИНФРА- М; Новосибирск Изд-во НГТУ, 2002. 12. Уилсон Р. Введение в теорию графов. – М Мир, 1977. 13. Харари Ф. Теория графов. – М Мир. 14. Яблонский СВ. Введение в дискретную математику. – М Высш. шк, 2002. Использованы задачи с сайта www.zaba.ru Оглавление Введение ...............................................................................................................................................3 Комбинаторика Предмет комбинаторики. ................................................................................................................3 Правила суммы и произведения. ....................................................................................................5 Формула включения и исключения Размещения с повторениями Размещения без повторений .........................................................................................................11 Перестановки Перестановки с повторениями Сочетания Свойства чисел .........................................................................................................................17 Сочетания с повторениями. ..........................................................................................................19 Комбинаторика разбиений ............................................................................................................21 Вероятность ....................................................................................................................................26 Бином Ньютона ..............................................................................................................................28 Треугольник Паскаля Полиномиальная формула Рекуррентные соотношения Асимптотики ..................................................................................................................................42 Задачи по комбинаторике Общие правила комбинаторики ...............................................................................................44 Формула включения и исключения Размещения с повторениями Размещения без повторений .....................................................................................................48 Перестановки Сочетания Сочетания с повторениями .......................................................................................................51 Разные задачи .............................................................................................................................51 Комбинаторика разбиений ........................................................................................................55 Вероятность ................................................................................................................................58 Бином Ньютона. Полиномиальная формула. ..........................................................................60 Рекуррентные соотношения Задачи по теории графов ...................................................................................................................63 Основные определения и примеры графов. ............................................................................63 Матрицы, ассоциированные с графом .....................................................................................65 Изоморфизм графов Достижимость и связность Циклы ..........................................................................................................................................70 Алгоритмы обхода связного графа. .........................................................................................71 Деревья Двудольные графы Ориентированные графы и мультиграфы................................................................................78 Игры и головоломки ..................................................................................................................81 Плоские графы ...........................................................................................................................82 Стереографическая проекция ...................................................................................................83 Двойственные графы .................................................................................................................83 Раскраски графа .........................................................................................................................84 Список рекомендуемой литературы по теории графов Список литературы ............................................................................................................................89 91 Корнилов Петр Анатольевич Никулина Надежда Ивановна Семенова Ольга Геннадьевна Элементы дискретной математики Редактор Иванова НА. Подписано в печать 30.11.05 Формат бумаги х 1/16 Печ. л. 5.5 Заказ 123 Тираж 100 экз. Редакционно-издательский отдел Ярославского государственного педагогического университета имени К.Д.Ушинского (ЯГПУ) 150000, Ярославль, Республиканская, 108 ЛР №020080 от 19.12.97 |