Элементы дискретной математики. К. Д. Ушинского Элементы дискретной математики Ярославль, 2005 па. Корнилов, ни. Никулина, Семенова О. Г. Элементы дискретной математики. Учебное пособие
 Скачать 0.81 Mb.
|
|
77. Мышка грызет куб сыра с ребром 3, разбитый на 27 единичных кубиков. Когда мышка съедает какой-либо кубик, она переходит к другому кубику, имеющему общую грань с предыдущим. Может ли мышка съесть весь куб, кроме центрального кубика 78. Можно ли перевести шахматного коня с клетки а на клетку h8, побывав при этом на каждой клетке шахматной доски ровно один раз Алгоритмы обхода связного графа. 79. Перечислить вершины графа в порядке обхода а) в глубину в) в ширину. 1 2 3 4 6 7 8 72 80. Граф задан матрицей смежности. Найти · Какой-либо путь из вершины 2 в вершину 4; · кратчайший путь из вершины 2 в вершину 4; · кратчайшие пути из вершины 2 ко всем остальным вершинам. 1 2 3 4 5 6 7 8 9 10 1 0 1 0 0 1 0 0 0 0 0 2 1 0 1 0 0 0 0 0 1 0 3 0 1 0 1 0 0 0 0 0 0 4 0 0 1 0 1 1 0 1 1 0 5 1 0 0 1 0 0 0 0 0 0 6 0 0 0 1 0 0 1 0 0 0 7 0 0 0 0 0 1 0 1 0 1 8 0 0 0 1 0 0 1 0 0 0 9 0 1 0 1 0 0 0 0 0 0 10 0 0 0 0 0 0 1 0 0 0 81. На планете Глюк живет группа людей. Про некоторые пары людей известно, что они близкие родственники. Назовем Аи В родственниками, если Аи В близкие родственники, или найдется третий человек С, который по отдельности является родственником Аи родственником В. Опишите алгоритм нахождения всех родственников человека Х. 82. На клетчатом листе бумаги размером 10 х 10 закрашены некоторые клетки. Разрешается ходить по не закрашенным клеткам, переходя на каждом шаге вверх, вниз, вправо или влево. Описать алгоритм, отвечающий наследующие вопросы А. Есть ли путь из левой нижней клетки в правую верхнюю Б. Какое минимальное число шагов нужно сделать, чтобы пройти этот путь В. По каким клеткам при этом надо идти 83. В двузначном числе за один ход разрешается заменить любую цифру суммой цифр по модулю 10. Заданы два двузначных числа a и b. Написать программу, которая определяет можно ли построить цепочку ходов, которая переводит a в b; минимальную такую цепочку. В двузначном числе старшая цифра может быть и нулем. 84. На шахматной доске N х N, несколько клеток, которой вырезано, заданы две клетки. Построить минимальный путь коня из одной данной клетки в другую. 85. В таблице N x N, где N<13, клетки заполнены случайным образом цифрами от 0 до 9. Предложить алгоритм, позволяющий найти маршрут из клетки (1,1) в клетку (N,N) и удовлетворяющий следующим условиям · любые две последовательные клетки в маршруте имеют общую сторону · количество клеток маршрута минимально · из всех маршрутов, удовлетворяющих условиями, искомый маршрут тот, сумма цифр в клетках которого максимальна. 73 86. Имеются три пробирки. Вместимость каждой из них 100 миллилитров. Две пробирки из трех одинаково размечены. Деления нанесены произвольно и соответствуют целым количествам миллилитров. Изначально одна из пробирок с делениями наполнена 100 миллилитрами кваса, а остальные пустые. Описать алгоритм, который выясняет, можно ли поместить в пробирку без делений один миллилитр кваса и, если да, то находит минимальное число необходимых для этого переливаний. Каждое переливание из одной пробирки в другую можно проводить до тех пор, пока либо первая из них не станет пустой, либо одна из пробирок не окажется заполненной до какого-либо деления. 87. Имеется расписание беспосадочных авиарейсов. Составить оптимальный алгоритм определяющий, можно ли из пункта А попасть в пункт В. 88. Имеется атлас автомобильных дорог с указанием расстояний между городами. Составить оптимальный алгоритм нахождения минимального пути между двумя городами. Деревья. 89. Докажите, что граф, в котором любые две вершины соединены ровно одной цепью, является деревом. 90. Докажите, что в дереве любые две вершины соединены ровно одной цепью. 91. Докажите, что в дереве с р вершинами р ребро. 92. Докажите, что связный графу которого число ребер на единицу меньше числа вершин, является деревом. 93. Докажите, что в дереве есть вершина, из которой выходит ровно одно ребро (такая вершина называется висячей. 94. Докажите, что в любом нетривиальном дереве имеются, по крайней мере, две висячие вершины. 95. Докажите, что при удалении любого ребра из дерева оно превращается в несвязный граф. 96. Какое максимальное число висячих вершин может иметь дерево, обладающее 9 вершинами 97. В графе все вершины имеют степень 3. Докажите, что в нем есть цикл. 98. В парке Лотос невозможно найти такой маршрут для прогулок по его дорожкам, который начинается и оканчивается водной и той же точке и каждую дорожку содержит не более одного раза. Докажите, что некоторые дорожки парка приводят в тупик. 99. В стране 101 городи некоторые из них соединены дорогами. При этом любые два города соединяет ровно один путь. Сколько в этой стране дорог 100. Докажите, что в любом связном графе можно удалить вершину вместе со всеми выходящими из нее ребрами так, чтобы он остался связным. 101. Сколько ребер нужно удалить из связного графа, имеющего q ребер и p вершин, чтобы получить дерево, содержащее все вершины этого графа. 102. Докажите, что полный двудольный граф с n вершинами водной доле и m вершинами в другой имеет не менее mn-m-n+1 различных циклов 74 103. Найдите цикломатическое число для графов · К · К · W n ; · графа Петерсона; · любого связного регулярного графа с n вершинами степени регулярности r. 104. В некоторой стране 30 городов, причем каждый соединен с каждым дорогой. Какое наибольшее число дорог можно закрыть на ремонт так, чтобы из каждого города можно было проехать в каждый 105. В несвязном графе с 5 компонентами связности любое ребро является мостом. Сколько вершин в графе, если ребер 115? (1 балл) 106. Постройте остовы графа, изображенного на рисунке методами поискав ширину ив глубину. 107. Найдите какие-нибудь остовные деревья для графов К, К, ив графе Петерсона. 108. Найти минимальный каркас графа, изображенного на рисунке, используя алгоритм Краскала. 109. Постройте каркас минимального веса для графа заданного матрицей весов (2 балла) 0 20 ∞ ∞ ∞ 15 ∞ 20 0 ∞ ∞ 1 ∞ 3 ∞ ∞ 05 2 ∞ 2 ∞ ∞ 5 0 3 ∞ 1 ∞ 1 2 3 0 10 ∞ 15 ∞ ∞ ∞ 10 0 ∞ ∞ 3 2 1 ∞ ∞ 0 0 2 ∞ ∞ ∞ 7 10 2 0 10 ∞ ∞ 1 0 ∞ 10 0 2 ∞ ∞ ∞ ∞ ∞ 2 0 5 1 ∞ ∞ ∞ ∞ 5 0 3 ∞ 7 1 ∞ 1 3 0 2 10 ∞ ∞ ∞ ∞ 2 0 0 ∞ ∞ ∞ ∞ 3 2 ∞ 0 10 ∞ ∞ 4 ∞ ∞ 10 0 ∞ ∞ 4 ∞ ∞ ∞ ∞ 0 2 3 ∞ ∞ ∞ ∞ 2 0 1 ∞ 3 4 4 3 1 0 1 2 ∞ ∞ ∞ ∞ 1 0 75 110. Найти каркас минимального веса для полного графа на множестве вершин (х, х, х, х, как показано на рисунке, с весами ребер, определенных как расстояния между вершинами. 111. На строительном участке нужно создать телефонную сеть, соединяющую все бытовки. Для того чтобы телефонные линии не мешали строительству, их решили проводить вдоль дорог. Схема участка изображена на рисунке, где бытовкам соответствуют вершины графа и указаны длины дорог между ними. Каким образом провести телефонные провода, чтобы их общая длина была минимальной 112. Необходимо построить систему нефтепроводов, которые должны соединять семь нефтеочистительных заводов (Н, Н, Н, Н, Н, Н, Н) , принадлежащих некоторой компании, спортом (П, куда поступает импортируемая сырая нефть. Стоимость прокладки нефтепровода между любыми двумя пунктами составляет 5000 долларов в расчете на одну милю. расстояния между всеми парами вершин задаются в следующей таблице П Н Н Н Н Н Н Н П 0 5 6 8 2 6 9 10 Н 0 4 10 5 8 6 10 Н 0 11 8 4 9 10 Н 0 10 3 6 7 Н 0 2 5 9 Н 0 10 5 Н 0 8 Н 0 Найдите минимальную стоимость прокладки нефтепровода. 113. Борцовский турнир с 13 участниками проводится по олимпийской системе, при которой проигравший выбывает. На одну встречу, с учетом подготовки к ней и отдыха 4 7 100 380 240 210 170 150 180 5 6 2 1 200 3 100 260 участника, отводится один час. Сколько времени нужно, чтобы провести турнир, если в распоряжении организаторов только 5 борцовских ковров 114. Есть бактерия, которая делится на 3 бактерии. В дальнейшем появляющиеся бактерии могут делиться на 4 бактерии, могут делиться на две, а могут и не делиться. Образовалось 102 бактерии. Определите число делений, если известно, что число бактерий, разделившихся на две враз больше, чем число бактерий, разделившихся на четыре. 115. Насыщенным углеводородом называется соединение углерода С, имеющего валентность 4, и водорода Р, имеющего валентность 1, в котором при заданном числе атомов углерода содержится наибольшее число атомов водорода. Напишите формулу насыщенного углеводорода, содержащего n атомов углерода. 116. Город имеет форму квадрата (100n x 100n) метров с (n+1) прямолинейной улицей, идущей параллельно одной стороне квадрата, и (n+1) прямолинейной улицей, идущей параллельно другой его стороне. Расстояние между любыми двумя соседними параллельными улицами – 100 метров, длина каждой улицы – 100n метров. Мэр города решил выполнить свое предвыборное обещание заасфальтировать за свой счет улицы так, чтобы с любого перекрестка на любой другой можно было проехать по асфальту. Конечно, мэр хочет истратить как можно меньше своих денег. Какой наименьшей длины асфальтовое покрытие улиц может сделать мэр 117. Несколько авиакомпаний решили связать авиалиниями 100 городов так, чтобы выполнялось два условия · любые два города были соединены беспосадочной линией не более чем одной компании · любая авиакомпания, пользуясь своими линиями, могла бы доставить пассажира из любого города в любой другой (возможно с пересадками. При каком наибольшем числе авиакомпаний такое решение осуществимо 118. Каждый член шайки, включая главаря, имеет не более двух подручных, знает только их телефонные номера и имеет собственный телефон. Ни один член шайки не может быть подручным сразу у двоих. Сформулируйте алгоритм, позволяющий главарю узнать численность шайки в двух случаях · никто из членов шайки, кроме главаря, не умеет считать · все члены шайки, кроме главаря, умеют считать. Двудольные графы. 119. Является ли двудольным графом · простая цепь · дерево 77 · полный граф 120. Докажите, что дерево является двудольным графом. Какие деревья являются полными двудольными графами. 121. В теннисном турнире каждый игрок команды синих встречается с каждым игроком команды красных. Число игроков в командах одинаково и не более восьми. Синие выиграли в четыре раза больше встреч, чем красные. Сколько человек в каждой из команд 122. Школьники на кружке решали 16 задачи. Каждый из 16 школьников решил по четыре задачи, и каждая задача была решена четырьмя школьниками. Доказать, что можно организовать разбор задач так, чтобы каждый рассказал одну решенную им задачу и чтобы все задачи были разобраны. 123. Каждый из учеников 9 А класса дружит стремя учениками 9 Б класса, а каждый из учеников 9 Б класса дружит стремя учениками 9 А класса. Докажите, что число учеников в обоих классах одинаково. 124. Строительному управлению для выполнения работы требуются каменщик плотник, водопроводчики слесарь. На эти должности имеются пять претендентов один может работать каменщиком, другой – плотником, третий – каменщиком и водопроводчиком и еще двое имеют по две специальности – водопроводчика и слесаря. Можно ли охватить весь фронт работ (используя четверых рабочих Если да, то подробно проверьте выполнение условия теоремы Холла. 125. В школе 4 кружка домоводство, математический кружек, компьютеный клуб и кружек английского языка. Пять человек из класса посещают эти кружки, причем один и тот же ученик может являться членом нескольких кружков. Можно ли выбрать старосту в каждом кружке так, чтобы ни один человек не был старостой сразу в двух кружках, в следующих случаях 1. Кружок домоводства посещают 1, 3 и 4 ученики, математический кружок – 1, 4 и 5, компьютерный клуб – 2, 3 и 5, кружок английского языка – 2, 4 и 5. 2. Кружок домоводства посещают 1 и 3 ученики, математический кружок – 2 и 3, компьютерный клуб – 2 и 1, кружок английского языка – 3. 3. Кружок домоводства посещают 1, 3 и 4 ученики, математический кружок – 2 и 5, компьютерный клуб – 2 и 5, кружок английского языка – 2. 126. Десять кандидатов готовятся к двум космическим экспедициям на Марс. Поскольку экспедиции будут продолжаться несколько лета их участники окажутся в замкнутом пространстве небольшого объема, то большое значение приобретает психологическая совместимость членов экипажа. Путем тестирования установлены пары кандидатов, присутствие которых водной и той же экспедиции было бы нежелательным. Результаты тестирования отражены в таблице. (Если на пересечении I строки j столбца находится знак «+», то участие I и j кандидатов водной экспедиции нежелательно) Разделите кандидатов на две группы для участия в экспедициях. 1 2 3 4 5 6 7 8 9 10 1 + + + 2 + + 3 + + 4 + + 5 + + 6 + + 7 + + + 8 + + + 9 + + 10 + + + Ориентированные графы и мультиграфы 127. Решите задачу 35. Граф может быть орграфом или мультиграфом. 128. В некотором государстве каждый город соединен с каждым дорогой. Сумасшедший король хочет ввести на дорогах одностороннее движение, так чтобы, выехав из любого города, в него нельзя было вернуться. Можно ли так сделать 129. Докажите, что на ребрах связного графа можно так расставить стрелки, чтобы из некоторой вершины можно было добраться по стрелкам до любой другой. 130. Доказать, что связный граф можно обойти, проходя по каждому ребру дважды. 131. Изобразите матрицы смежности и инцидентности ориентированного графа 132. Дана матрица смежности. Изобразить граф, ей соответствующий. а) 1 2 3 4 5 6 7 1 1 0 1 1 0 1 0 2 0 0 0 0 0 0 1 3 1 0 0 1 0 1 0 4 0 1 0 0 0 0 1 5 1 1 1 0 0 0 1 6 1 0 1 1 0 1 0 7 0 1 0 0 1 0 0 б) 1 2 3 4 5 1 1 2 0 0 1 2 0 0 3 0 0 3 0 0 2 1 0 4 1 0 1 0 1 5 1 0 0 0 0 133. Определите, какие из предложенных графов являются ориентируемыми. 79 134. Из города А в город Введут несколько дорог (карта дорог на рисунке. Найдите число маршрутов из А в В, учитывая, что при движении необходимо всегда приближаться кВ. Может ли в ориентированном графе полустепень захода каждой вершины быть равна 3, а полустепень исхода – 4? 136. В некоторой стране есть столица и еще 100 городов. Некоторые города (в том числе и столица) соединены дорогами с односторонним движением. Из каждого нестоличного города выходит 20 дороги в каждый такой город входит 21 дорога. Докажите, что в столицу нельзя проехать ни из одного города. 137. В некотором государстве 101 города) Каждый город соединен с каждым дорогой с односторонним движением, причем в каждый город входит 50 дороги из каждого города выходит 50 дорог. Докажите, что из любого города можно доехать в любой другой, проехав не более чем по двум дорогам б) Некоторые города соединены дорогами с односторонним движением, причем в каждый город входит 40 дороги из каждого города выходит 40 дорог. Докажите, что из любого города можно добраться до любого другого, проехав не более чем потрем дорогам 138. В стране Ориентация на всех дорогах введено одностороннее движение, причем из любого города в любой другой можно добраться, проехав не более чем по двум дорогам. Одну дорогу закрыли на ремонт так, что из каждого города по-прежнему можно добраться до каждого. Докажите, что для любых двух городов это можно сделать, проехав не более, чем потрем дорогам. 139. Найдите компоненты сильной связности графа, заданного матрицей смежности 1 2 3 4 5 6 7 8 9 1 0 1 1 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 3 0 1 0 1 0 0 0 0 0 4 0 0 0 0 1 0 0 0 0 5 0 0 0 0 0 1 0 0 0 6 0 0 0 0 0 0 1 0 0 7 0 0 0 1 0 0 0 0 0 8 0 0 1 0 0 0 0 0 0 9 1 0 0 0 0 0 0 1 0 140. Найдите компоненты сильной связности графа А В 2 5 1 4 3 80 141. Дана матрица смежности графа, определить, является ли он эйлеровым. Ответ обоснуйте. 1 2 3 4 5 6 7 1 0 1 1 0 0 0 1 2 0 0 1 0 1 0 0 3 0 1 0 0 0 0 1 4 1 0 0 0 1 1 0 5 1 0 0 1 0 0 0 6 1 0 0 1 0 0 0 7 0 0 0 1 0 1 0 142. Решите задачу 62, считая, что заданы матрицы смежности ориентированного графа. 143. На ребрах связного графа расставлены стрелки так, что для каждой вершины числа входящих и выходящих ребер равны. Докажите, что двигаясь по стрелкам, можно добраться от любой вершины до любой другой. 144. В связном неориентированном графе степени всех вершин четны. Докажите, что на ребрах этого графа можно расставить стрелки так, чтобы выполнялись следующие условия а) двигаясь по стрелкам, можно добраться от любой вершины до любой другой б) для каждой вершины числа входящих и выходящих ребер равны. 145. На плоскости отмечено некоторое конечное число точек. Некоторые пары точек являются началами и концами векторов, причем число векторов, выходящих из любой точки равно числу входящих вне. Найдите сумму векторов. 146. В некоторой стране каждый город соединен с каждым дорогой с односторонним движением. Докажите, что найдется город, из которого можно добраться в любой другой. 147. Несколько команд сыграли между собой круговой турнир по волейболу. Будем говорить, что команда А сильнее команды В, если либо А выиграла у В, либо существует команда С такая, что А выиграла у С, а Су В. а) Докажите, что есть команда, которая сильнее всех. б) Докажите, что команда, выигравшая турнир, сильнее всех. 148. Водном государстве 100 городов, и каждый соединен с каждым дорогой с односторонним движением. Докажите, что можно поменять направление движения на одной дороге так, чтобы от любого города можно было доехать до любого другого. 149. 20 команд сыграли круговой турнир по волейболу. Докажите, что команды можно занумеровать числами от 1 до 20 так, что я команда выиграла у й, я - у й, ..., я у й. 150. Докажите, что если победитель турнира по волейболу, проведенного по круговой системе, проиграл команде В, то существует команда С, выигравшая у В, у которой выиграл победитель. 81 151. Какие-то две команды набрали в круговом волейбольном турнире одинаковое число очков. Докажите, что найдутся команды А, В и С такие, что А выиграла у В, В выиграла у С, а С выиграла у А. Игры и головоломки 152. Два человека имеют кувшин молока в 8 литров, а также два пустых кувшина в 5 и 3 литра. Как они могут разделить молоко поровну |