Дискретная математика
Комбинаторика, теория множеств, теория графов, теория алгоритмов
Методические указания для выполнения расчетно-графических заданий
по курсу «Дискретная математика» для студентов дневного отделения
специальностей 010503 «Математическое обеспечение и администрирование информационных систем»», 230105 «Программное обеспечение вычислительной техники и автоматизированных систем»
Комсомольск-на-Амуре 2009
При выполнении расчетно-графических заданий следует строго придерживаться указанных ниже правил.
1. Выбор варианта осуществляется на практических занятиях преподавателем.
2. Расчетно-графическое задание и контрольная работа оформляется в тонкой тетради (или распечатывается на листах формата А4) чернилами любого цвета, кроме красного. Для замечаний рецензента оставляются поля. На обложке (титульном листе) указываются: фамилия, имя, отчество студента, его учебный шифр (серия и номер зачетной книжки), домашний адрес, а также наименование дисциплины. Текст расчетно-графического задания должен быть читаемым.
3. Решение задач следует располагать в порядке следования номеров, указанных в задании, сохраняя номера задач и записывая исходные данные. Если несколько задач имеют общую формулировку, то при оформлении решения общие условия заменяют конкретными данными.
4. Решения задач следует оформлять аккуратно, подробно объясняя ход решения.
5. После получения проверенной работы необходимо исправить в ней отмеченные рецензентом ошибки и недочеты. Работа над ошибками, как правило, делается в той же тетради. При необходимости, работу над ошибками допускается выполнять в новой тетради, но при отсылке на рецензирование необходимо приложить первоначальный вариант выполнения работы.
6. Задачи, отмеченные *, приведенные в методических указаниях, не являются обязательными для выполнения.
РАСЧЕТНО-ГРАФИЧЕСОЕ ЗАДАНИЕ 1
Множества и отношения, теория графов
Задача 1 Изобразить диаграмму Хассе частично упорядоченного множества.
1. Изобразить диаграмму Хассе множества подмножеств из {0,1,2,3}, упорядоченных отношением включения.
2. Изобразить диаграмму Хассе множества подмножеств из {0,1,2,3,4} упорядоченных отношением включения.
3. Изобразить диаграмму Хассе множества подмножеств из {0,1,2,{3}}, упорядоченных отношением включения.
4 Изобразить диаграмму Хассе множества подмножеств из {{0,1},{2,3}}, упорядоченных отношением включения.
5 Изобразить диаграмму Хассе множества подмножеств из {0,{1,2},3}, упорядоченных отношением включения.
6. Изобразить диаграмму Хассе множества делителей числа 1000, упорядоченного отношением делимости.
7. Изобразить диаграмму Хассе множества делителей числа 360, упорядоченного отношением делимости.
8. Изобразить диаграмму Хассе множества делителей числа 120, упорядоченного отношением делимости.
9. Изобразить диаграмму Хассе множества делителей числа 125, упорядоченного отношением делимости.
10. Изобразить диаграмму Хассе множества делителей числа 48, упорядоченного отношением делимости.
11. Изобразить диаграмму Хассе множества подмножеств из {{0,1},2,3,4}, упорядоченных отношением включения.
12. Изобразить диаграмму Хассе множества подмножеств из {0,{1,2},3,4} упорядоченных отношением включения.
13. Изобразить диаграмму Хассе множества подмножеств из {0,{1,2},{3,4}}, упорядоченных отношением включения.
14 Изобразить диаграмму Хассе множества подмножеств из {0,1,2,{3,4}}, упорядоченных отношением включения.
15 Изобразить диаграмму Хассе множества подмножеств из {0,1,{2,3},4}, упорядоченных отношением включения.
16. Изобразить диаграмму Хассе множества делителей числа 100, упорядоченного отношением делимости.
17. Изобразить диаграмму Хассе множества делителей числа 128, упорядоченного отношением делимости.
18. Изобразить диаграмму Хассе множества делителей числа 1024,упорядоченного отношением делимости.
19. Изобразить диаграмму Хассе множества делителей числа 192, упорядоченного отношением делимости.
20. Изобразить диаграмму Хассе множества делителей числа 200, упорядоченного отношением делимости.
Пример решения задачи 1
Пусть (X,£) – частично упорядоченное множество. Множество ]x,y[ = {vÎX: x<v<y} называется открытым интервалом с концами.
Диаграммой Хассе называется ориентированный граф (V,A) с V=X и A={(u,v): u<v и ]u,v[ = Æ}.
Пример 1
Пусть P({0,1,2}) – множество подмножеств множества {0,1,2}, упорядоченное отношением Í.
Диаграммой Хассе будет ориентированный граф:
Предполагаются, что ребра направлены сверху вниз.
Рассмотрим множество делителей (Dn, |) натурального числа n³1, упорядоченное отношением
делимости a | b Û a – делитель числа b (в этом случае говорят, что a – делит b).
Пример 2
Пусть p и q – различные простые числа >1. Диаграмма Хассе множества (Dn, |) с n=p2q показана на рисунке
В общем случае диаграмма Хассе частично упорядоченного множества (Dn, |) состоит из ребер m-мерного параллелепипеда, где m – число различных простых делителей числа n.
Задача 2 Ответить на вопрос, либо доказать соответствующее утверждение
1. Доказать, что граф имеет четное число вершин с нечетными степенями.
2. При встрече студентов состоялось 15 рукопожатий, трое человек сделали по 4 рукопожатия, а другие – по 3. Сколько было студентов.
3. Может ли существовать группа из 23 человек, каждый из которых знаком с пятью другими?
4. В соревнованиях по шахматам по круговой системе участвуют 5 человек. Все, кроме Иванова и Петрова, сыграли различное число партий. Сколько партий сыграли Иванов и Петров?
5. Можно ли нарисовать без отрыва карандаша граф K6, у которого удалено одно ребро.
6. 
7. Для полного графа имеет место: 
.
8. Для дискретного графа G с n вершинами fG(q)=qn
9. Для полного графа с n вершин число остовных деревьев равно nn-2
10. Доказать, что сумма коэффициентов i-й строки матрицы смежности равна степени i-й вершины.
11. Сколько компонент связности имеет лес, содержащий 76 вершин и 53 ребра.
12. В компании, состоящей из пяти студентов, среди любых трех найдутся два знакомых и два незнакомых. Доказать, что компанию можно рассадить за круглым столом таким образом, что любые два соседа будут знакомы.
13. Доказать, что среди 6 человек найдется тройка знакомых, или тройка незнакомых людей.
14. Найти хроматическую функцию графа An:
15. Найти хроматическое число графа, полученного удалением одного ребра из полного графа Kn. Двух ребер. Трех ребер, составляющих треугольник.
16. Докажите, что дерево является двудольным графом.
17. Найти все максимальные поддеревья графа, полученного удалением одного ребра из графа K4.
18. Кратчайший путь соединяющий вершины u и v в графе называется геодезическим путем между вершинами. Его длина обозначается d(u,v). Диаметром D(G) графа называется длина самого длинного геодезического пути в этом графе, т.е. D(G)=max{d(u,v): u,vÎV}. Найти диаметры графов
(1) K5;
(2)
(3) Для дерева.
19. Доказать, что Числа Каталана равны 
.
20. Доказать, что для дерева T имеющего число вершин n хроматическая функция равна fG(q)=q(q – 1)n-1
Пример решения задачи 2. Пусть d(v) обозначает степень вершины v. Доказать, что для произвольного графа (V,E) верно соотношение
(Теорема Эйлера)
Доказательство. Рассмотрим упорядоченные пары (v,g), состоящие из вершины v инцидентой ребру g. Количество таких пар равно сумме степеней вершин. С другой стороны, оно равно удвоенному числу ребер. Что и требовалось доказать.
Задача 3 Определить минимальный путь в соответствии с алгоритмом Дейкстры из v1 во все другие в нагруженном графе, заданном матрицей длин дуг, построить минимальное остовное дерево. Если в матрице указана бесконечность в качестве элемента, то дуги нет.
| 1. |
| 3. |
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 2. |
| 4. |
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 5. |
| 6. |
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 7. |
| 8. |
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 9. |
| 10. |
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 11. |
| 12. |
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 13. |
| 14. |
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 15. |
| 16. |
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 17. |
| 18. |
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 19. |
| 20. |
|
Пример решения.
Рассмотрим выполнение алгоритма Дейкстры на примере графа, показанного на рис. 3. Пусть требуется найти расстояния от 1-й вершины до всех остальных.
Рис. 3 Граф
Первый шаг. Рассмотрим шаг алгоритма Дейкстры для нашего примера. Минимальную метку имеет вершина 1. Её соседями являются вершины 2, 3 и 6.
Первый по очереди сосед вершины 1 — вершина 2, потому что длина пути до неё минимальна. Длина пути в неё через вершину 1 равна кратчайшему расстоянию до вершины 1 + длина ребра, идущего из 1 в 2, то есть 0 + 7 = 7. Это меньше текущей метки вершины 2, поэтому новая метка 2-й вершины равна 7.
Аналогичную операцию проделываем с двумя другими соседями 1-й вершины — 3-й и 6-й.
Все соседи вершины 1 проверены. Текущее минимальное расстояние до вершины 1 считается окончательным и пересмотру не подлежит (то, что это действительно так, впервые доказал Дейкстра). Вычеркнем её из графа, чтобы отметить, что эта вершина посещена.
Второй шаг. Шаг алгоритма повторяется. Снова находим «ближайшую» из непосещенных вершин. Это вершина 2 с меткой 7.
Снова пытаемся уменьшить метки соседей выбранной вершины, пытаясь пройти в них через 2-ю. Соседями вершины 2 являются 1, 3, 4.
Первый (по порядку) сосед вершины 2 — вершина 1. Но она уже посещена, поэтому с 1-й вершиной ничего не делаем.
Следующий сосед вершины 2 — вершина 3. Если идти в неё через 2, то длина такого пути будет = 7 + 10 = 17. Но текущая метка третьей вершины равна 9<17, поэтому метка не меняется.
Ещё один сосед вершины 2 — вершина 4. Если идти в неё через 2-ю, то длина такого пути будет = кратчайшее расстояние до 2 + расстояние между вершинами 2 и 4 = 7 + 15 = 22. Поскольку 22< 
, устанавливаем метку вершины 4 равной 22.
Все соседи вершины 2 просмотрены, замораживаем расстояние до неё и помечаем её как посещенную.
Третий шаг. Повторяем шаг алгоритма, выбрав вершину 3. После её «обработки» получим такие результаты:
Дальнейшие шаги. Повторяем шаг алгоритма для оставшихся вершин (Это будут по порядку 6, 4 и 5).
Завершение выполнения алгоритма. Алгоритм заканчивает работу, когда вычеркнуты все вершины. Результат его работы виден на последнем рисунке: кратчайший путь от вершины 1 до 2-й составляет 7, до 3-й — 9, до 4-й — 20, до 5-й — 20, до 6-й — 11.
Для данного графа построить минимальное остовное дерево.
Задача Построить минимальное остовное дерево нагруженного графа приведенного на рисунке
Решение.
На рисунке приведена последовательность графов, получаемых в результате выполнения алгоритма построения МОД нагруженного графа. Причем, МОД(G) = 19.
Задача 4 Принцип Дирихле.
Варианты
1. В мешке лежат шарики 2-х разных цветов (много белых и много черных). Какое наименьшее количество шариков надо на ощупь вынуть из мешка, чтобы среди них заведомо оказались два одного цвета.
2. Дано 233 целых числа. Доказать, что разность каких-то двух из них делится на 232.
3. В строку выписано 5 натуральных чисел: a1,a2,a3,a4,a5. Докажите, что- либо одно из них делится на 5, либо сумма нескольких рядом стоящих чисел делится на 5.
4. На олимпиаде 10 школьников решили в сумме 35 задач, причем среди них были решившие ровно одну, ровно две и ровно три задачи. Доказать, что кто-то из них решил не менее 5 задач.
5. Докажите, что равностронний треугольник нельзя покрыть двумя меньшими равносторонними треугольниками.
6. В квадрат со стороной 1 м бросили произвольным способом 51 точку. Докажите, что какие-то три из них можно накрыть квадратиком со стороной 0,2 м.
7. Поставить на шахматную доску наибольшее число ферзей (королев) так, чтобы ни один из них не мог взять другого. Для читателей незнакомых с шахматной игрой, сообщим, что ферзи могут бить по горизонталям, вертикалям и диагоналям.
8. За круглым столом сидят 100 человек, причем более половины из них - рыцари. Доказать, что какие-то два рыцаря сидят напротив друг друга
9. Кот Базилио пообещал Буратино открыть великую тайну, если он составит чудесный квадрат 6 х 6 из чисел +1, -1, 0 так, чтобы все суммы по строкам, по столбцам и по большим диагоналям были различны. Помогите Буратино.
10. На плоскости проведено 12 прямых. Докажите, что какие-то две из них образуют угол не больше 15о.
11. Квадратная таблица (2 n + 1) x (2 n + 1) заполнена числами от 1 до 2 n + 1 так, чтобы в каждой строке и в каждом столбце были представлены все эти числа. Докажите, что если это расположение симметрично относительно главной диагонали, то на главной диагонали тоже представлены все эти числа.
12. Комиссия из 60 человек провела 40 заседаний, причём на каждом заседании присутствовало ровно 10 членов комиссии. Докажите, что какие-то два члена комиссии встречались на её заседаниях по крайней мере дважды.
13. На столе лежат 50 правильно идущих часов. Докажите, что в некоторый момент сумма расстояний от центра стола до концов минутных стрелок будет больше, чем сумма расстояний от центра стола до центров часов.
14. Каждая из 9 прямых разбивает квадрат на два четырёхугольника, площади которых относятся как 2:3. Докажите, что по крайней мере три из этих прямых проходят через одну точку.
15. Пятеро программистов получили на всех зарплату - 1750 долларов. Каждый из них хочет купить себе новый компьютер за 360 долларов. Докажите, что кому-то из них это не светит.
16. На планете в звездой системе Тау Кита суша занимает больше половины площади. Доказать, что таукитяне смогут прорыть прямой туннель через центр планеты так, чтобы он соединял сушу с сушей.
17. На собеседование пришли 65 школьников. Им предложили 3 контрольных работы. За каждую контрольную ставилась одна из оценок: 2,3,4 или 5. Верно ли, что найдутся два школьника, получившие одинаковые оценки на контрольных?
18. На земле больше 4 миллиардов человек, которые моложе 100 лет. Докажите, что на Земле есть два человека, родившихся в одну и ту же секунду.
19. На карьере добыли 36 камней. Их веса соответственно 490 кг, 495 кг, 500 кг, …, 665 кг (арифметическая прогрессия). Можно ли увезти эти камни на семи трёхтонных грузовиках?
20. Докажите, что из любых 52 целых чисел всегда можно выбрать два, сумма или разность которых делится на 100
Пример решения
В самолёте летят 380 пассажиров. Докажем, что, по крайней мере, двое из них родились в один и тот же день года.
Сформулируем принцип Дирихле.
Если имеется n ящиков, в которых находится в общей сложности не менее n+1 предмета, то непременно есть ящик, в котором лежат, по крайней мере, 2 предмета.
Другая формулировка: не существует инъекции более мощного множества в менее мощное.
Решение. Всего в году 365 или 366 дней, а пассажиров в самолёте 380 – значит, их дни рождения не могут приходиться только на различные даты. Вообще, если пассажиров больше, чем 366, то хотя бы у двоих дни рождения совпадают. А вот если пассажиров 366, не исключено, что все они родились в разные дни года, но это маловероятно. (Согласно теории вероятностей, в случайно выбранной группе численностью свыше 22 человек совпадение дней рождения у некоторых из них более вероятно, нежели то, что у всех дни рождения приходятся на разные дни года).
Задача 5 Комбинаторные конфигурации
1. Сколько слов можно образовать из букв слова фрагмент, если слова должны состоять:
(а) из восьми букв, (б) из семи букв, (в) из трех букв?
2. Сколько существует различных автомобильных номеров, которые состоят из пяти цифр, а) если первая из них не равна нулю; б) если номер состоит из одной буквы латинского алфавита, за которой следуют четыре цифры, отличные от нуля?
3. Сколькими способами можно расставить на полке семь книг, если (а) две определенные книги должны всегда стоять рядом, (б) эти две книги не должны стоять рядом?
4. Сколькими способами из восьми человек можно избрать комиссию, состоящую из пяти членов?
5. Компания из двадцати мужчин разделяется на три группы, в первую из которых входят три человека, во вторую — пять и в третью — двенадцать. Сколькими способами они могут это сделать? (Ответ записать в виде произведения сомножителей, не вычисляя его.)
6. Сколькими способами можно отобрать несколько фруктов из семи яблок, четырех лимонов и девяти апельсинов? (Мы считаем, что фрукты одного вида неразличимы.)
7. Сколько четырехбуквенных слов можно образовать из букв слова сапфир? 2) Сколько среди них таких, которые не содержат буквы р? 3) Сколько таких, которые начинаются с буквы с и оканчиваются буквой р?
8. Сколько пятибуквенных слов, каждое из которых состоит из трех согласных и двух гласных, можно. образовать из букв слова уравнение?
9. В соревновании принимают участие 8 спортсменов. Сколькими способами могут быть разделены медали (золотые, серебряные и бронзовые?)
10. Доказать, что 
11. Доказать, что 
12. Сколькими способами можно разложить число 1024 в произведение трех натуральных чисел, каждое из которых больше 2
13. Найти количество десятичных неотрицательных целых чисел, состоящих цифр, расположенных в неубывающем порядке.
14. Сколько существует шашечных позиций, состоящих из 10 белых и 10 черных шашек?
15. В группе 20 студентов. Одному человеку положено выдать надбавку к стипендии в размере 1000 рублей. Двум – по 500, трем по 300. Сколькими способами это можно сделать?
16. Найдите вероятность того, что наудачу выбранный член последовательности заданный формулой общего члена а 
= n(n + 2)/ 3, где n = 1, 2,…,8, есть целое число.
17. Набирая номер телефона, абонент забыл последние три цифры и, помня лишь, что эти цифры различные, набрал их наудачу. Найти вероятность того, что набраны нужные цифры.
18. Сколько различных семизначных чисел можно составить из цифр числа 7788899?
19. Имеется 25 российских и 15 зарубежных марок. Какова вероятность того, что из пяти выбранных наугад марок окажется 3 российские и 2 зарубежные марки?
20. Двое по очереди бросают монету, причем выигрывает тот, у которого раньше выпадет «орел». Оцените вероятность выигрыша для первого и второго игроков. Для этого проведите необходимое, на ваш взгляд, количество случайных экспериментов с помощью таблицы случайных чисел.
Пример решения Сколько различных перестановок можно образоватьизо всех букв слова перестановка? Сколько из них начинается с буквы п и оканчивается буквой а?
Решение задачи:
В слове перестановка 12 букв, из них повторяются 2 буквы е и две буквы а. Число пер
