УНІВЕРСИТЕТ РАДІОЕЛЕКТРОНІКИ

ХАРКІВСЬКИЙ НАЦІОНАЛЬНИЙ

УНІВЕРСИТЕТ РАДІОЕЛЕКТРОНІКИ

МЕТОДИЧНІ ВКАЗІВКИ

До практичних занять з дисципліни

«ДИСКРЕТНА МАТЕМАТИКА»

Частина 2

Харків 2014

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ

ХАРКІВСЬКИЙ НАЦІОНАЛЬНИЙ

УНІВЕРСИТЕТ РАДІОЕЛЕКТРОНІКИ

МЕТОДИЧНІ ВКАЗІВКИ

до практичних занять з дисципліни

«ДИСКРЕТНА МАТЕМАТИКА»

(частина 2)

для студентів усіх форм навчання напряму

6.050101 – Комп’ютерні науки

ЗАТВЕРДЖЕНО

кафедрою ІУС.

Протокол № 12 від 16.05.2014.

Харків 2014

Методичні вказівки до практичних занять з дисципліни «Дискретна математика» (частина 2) для студентів усіх форм навчання напряму 6.050101 – Комп’ютерні науки / Упоряд.: Н.В. Васильцова, Л.Е. Чала. – Харків: ХНУРЕ, 2014. – 76 с.

Упорядники: Н.В. Васильцова,

Л.Е. Чала

Рецензент В.О. Філатов, д-р техн. наук, проф. кафедри ШІ.

ЗАГАЛЬНІ ПОЛОЖЕННЯ............................................................................ 5

1 ОСНОВНІ ПРАВИЛА КОМБІНАТОРИКИ. МОДЕЛІ

КОМБІНАТОРНИХ КОНФІГУРАЦІЙ......................................................... 6

1.1 Мета заняття......................................................................................... 6

1.2 Методичні вказівки з організації самостійної роботи студентів........ 6

1.3 Контрольні запитання і завдання........................................................ 7

1.3.1 Контрольні запитання................................................................... 7

1.3.2 Контрольні завдання..................................................................... 8

1.4 Приклади аудиторних і домашніх задач............................................ 10

2 УРНОВІ СХЕМИ ВИРІШЕННЯ КОМБІНАТОРНИХ ЗАДАЧ................ 16

2.1 Мета заняття......................................................................................... 16

2.2 Методичні вказівки з організації самостійної роботи студентів........ 16

2.3 Контрольні запитання і завдання........................................................ 17

2.3.1 Контрольні запитання................................................................... 17

2.3.2 Контрольні завдання..................................................................... 17

2.4 Приклади аудиторних і домашніх задач............................................ 18

3 СПОСОБИ ЗАДАННЯ ГРАФІВ. ОПЕРАЦІЇ НАД ГРАФАМИ............... 20

3.1 Мета заняття......................................................................................... 20

3.2 Методичні вказівки з організації самостійної роботи студентів........ 20

3.3 Контрольні запитання і завдання........................................................ 21

3.3.1 Контрольні запитання................................................................... 21

3.3.2 Контрольні завдання..................................................................... 22

3.4 Приклади аудиторних і домашніх задач............................................ 25

4 ЗВ’ЯЗНІСТЬ ГРАФІВ. ЕЙЛЕРОВІ ТА ГАМІЛЬТОНОВІ ГРАФИ.......... 36

4.1 Мета заняття......................................................................................... 36

4.2 Методичні вказівки з організації самостійної роботи студентів........ 36

4.3 Контрольні запитання і завдання........................................................ 37

4.3.1 Контрольні запитання................................................................... 37

4.3.2 Контрольні завдання..................................................................... 37

4.4 Приклади аудиторних і домашніх задач............................................ 42

5 ДЕРЕВА. АЛГОРИТМИ ПОБУДОВИ ОСТОВНОГО ДЕРЕВА.............. 47

5.1 Мета заняття......................................................................................... 47

5.2 Методичні вказівки з організації самостійної роботи студентів........ 47

5.3 Контрольні запитання і завдання........................................................ 48

5.3.1 Контрольні запитання................................................................... 48

5.3.2 Контрольні завдання..................................................................... 48

5.4 Приклади аудиторних і домашніх задач............................................ 50

6 ВІДШУКАННЯ НАЙКОРОТШИХ ВІДСТАНЕЙ МІЖ
ВЕРШИНАМИ ГРАФА (МЕРЕЖІ................................................................ 59

6.1 Мета заняття......................................................................................... 59

6.2 Методичні вказівки з організації самостійної роботи студентів........ 59

6.3 Контрольні запитання і завдання........................................................ 60

6.3.1 Контрольні запитання................................................................... 60

6.3.2 Контрольні завдання..................................................................... 60

6.4 Приклади аудиторних і домашніх задач............................................ 62

7 ЗАДАЧІ ПРО МАКСИМАЛЬНУ ТЕЧІЮ І
МІНІМАЛЬНИЙ РОЗРІЗ У МЕРЕЖІ............................................................ 66

7.1 Мета заняття......................................................................................... 66

7.2 Методичні вказівки з організації самостійної роботи студентів........ 66

7.3 Контрольні запитання і завдання........................................................ 66

7.3.1 Контрольні запитання................................................................... 66

7.3.2 Контрольні завдання..................................................................... 67

7.4 Приклади аудиторних і домашніх задач............................................ 69

Перелік посилань........................................................................................... 75

ЗАГАЛЬНІ ПОЛОЖЕННЯ

Дисципліна «Дискретна математика» входить до складу дисциплін
циклу природничо-наукової підготовки бакалаврів з напряму 6.050101 – «Комп’ютерні науки» і є однією з базових математичних дисциплін
цього циклу.

Матеріал, який пропонується для вивчення другої частини дисципліни, складається з таких розділів: «Основи комбінаторного аналізу», «Основні поняття теорії графів».

Добір і викладення практичного матеріалу цих розділів дисципліни виконано з урахуванням вимог фундаментальної освіти з комп’ютерних наук, інформаційних технологій, сучасних інженерних і соціально-економічних напрямів з високим рівнем автоматизації та комп’ютеризації.

Методичні вказівки призначені для студентів молодших курсів, які спеціалізуються в галузі комп’ютерних наук і зобов’язані використовувати отримані практичні знання і навички під час проектування та упровадження інформаційно-управляючих систем і систем штучного інтелекту. Однак практичний матеріал з дисципліни «Дискретна математика» буде також корисним для тих, хто намагається підвищити кваліфікацію в напрямах (розділах дисципліни), перелічених вище.

Для вивчення другої частини дисципліни «Дискретна математика» студент повинен мати знання математики в обсязі середньої школи і деякі основні поняття з розділів дисципліни з вищої математики (зокрема, теорії матриць).

У методичні вказівки з дисципліни «Дискретна математика» входить перелік літератури (підручники, навчальні посібники і монографії), яку можна використовувати для уточнювання матеріалу або, за бажанням, для більш глибокого вивчення деяких теоретичних положень і практичних прикладів.

Завдання 12.

Студенти вивчають 14 предметів. Скільки існує способів, якими можна скласти розклад занять на суботу, якщо в цей день має бути 5 різних занять?

Завдання 13. Розглянемо множину . Треба знайти число
2-сполучень із чотирьох елементів із необмеженими повтореннями.

Завдання 14. У поштовому відділенні продаються листівки 10 видів. Скількома способами можна купити в ньому 12 листівок? Скількома способами можна купити в ньому 8 листівок? Скількома способами можна купити в ньому 8 різних листівок?

Завдання 15. На пошті є 5 видів листівок і 8 видів марок. Якою кількістю способів можна купити 12 листівок і 12 марок?

Завдання 16. Скількома способами можна призначити на чергування з охорони суспільного порядку групу з п’яти студентів і одного викладача, якщо маємо 15 студентів і 4 викладачі?

Завдання 17. Визначити коефіцієнт при в розкладанні за біномом Ньютона.

Завдання 18. Знайти розклад виразу на основі формули бінома Ньютона.

Завдання 19. Обчислити за допомогою бінома Ньютона вираз .

Завдання 20. Знайти розкладання за поліноміальною формулою .

Завдання 21. Записати формулу включень і виключень для випадку, коли число ознак, які нас цікавлять, дорівнює п’яти.

Завдання 22. Скільки існує цілих чисел від 0 до 9999, що не поділяються ні на 3, ні на 4, ні на 5.

Завдання 23. Знайти кількість цілих додатних чисел, які не перевищують 200 і не діляться на кожне з простих чисел: а) 2, 3, 5; б) 7, 11, 13.

Завдання 24. Під час підведення підсумків сесії виявилося, що склали на «добре» і «відмінно» фізику – 60% студентів, вищу математику – 50%, дискретну математику – 50%, фізику і вищу математику – 30%, фізику і дискретну математику – 30%, вищу математику і дискретну математику – 20%, усі три предмети – 10%. Скільки студентів склали на «добре» і «відмінно» точно два предмети? Скільки відсотків студентів одержали оцінки нижче «добре» з усіх трьох предметів?

1.4 Приклади аудиторних і домашніх завдань

Завдання 1. З міста А в місто В відправляється 10 потягів, 5 літаків і
3 автобуси. Скількома способами однієї людині можна дібратися з міста А
в місто В?

Розв’язок. За правилом суми всього існує 10+5+3=18 способів.

Завдання 2. На танцювальному майданчику є 17 юнаків і 21 дівчина. Скільки танцювальних пар вони можуть скласти?

Розв’язок. Спочатку виберемо юнака. Це можна зробити 17 способами. Після цього кожний юнак вибере собі партнершу (21 спосіб). За правилом добутку вибір упорядкованої множини танцювальних пар (юнак, дівчина) становить .

Завдання 3. Скількома способами можна вибрати 3 різні фарби, якщо є п’ять різних фарб?

Розв’язок. Порядок вибору фарб неважливий, тому кількість способів вибору можна обчислити за формулою .

Завдання 4. Нехай . Побудувати різні перестановки множини по 2 і по 3 елементи.

Розв’язок. 2-перестановками множини є , , , , , . Їхня кількість . 3-перестановками множини є , , , , , . Їхня кількість .

Їхня кількість дорівнює .

Завдання 5. Кілька людей сідають за круглий стіл. Вважатимемо, що два способи розміщення збігаються, якщо кожна людина має тих самих сусідів в обох випадках. Скількома різними способами можна розмістити за столом 11 осіб?

Розв’язок. Якби місця за столом були нумеровані, то на перше місце можна було б посадити кожного з 11, тобто 11 способами, на друге місце – кожного з 10, що залишилися і т.д. Оскільки треба зайняти 11 місць і є 11 осіб, то за правилом добутку маємо (11!) способів. Але оскільки місця не нумеровані та при переміщенні усіх на одне місце за годинниковою стрілкою (чи проти її) сусідство зберігається, то кількість способів треба зменшити в 11 разів. Крім того, сусідство зберігається при симетричному відображенні щодо діаметра, отже, кількість треба зменшити ще вдвічі.

Остаточна кількість способів розміщення виявляється рівною . У загальному випадку, коли за круглим столом треба розсадити людин, кількість способів дорівнює .

Завдання 6. У кімнаті студентського гуртожитку живуть троє студентів. У них є 4 чашки, 5 блюдець і 6 чайних ложок (усі чашки, блюдця і ложки відрізняються одне від одного). Скількома способами вони можуть накрити стіл для чаювання (кожний одержує одну чашку, одне блюдце й одну ложку)?

Розв’язок. Чашки можна розставити способами, блюдця способами і чайні ложки способами. Усього за правилом добутку накрити стіл для чаювання можна способами.

Завдання 7. Рота складається з 3 офіцерів, 6 сержантів і 60 рядових. Скількома способами можна виділити з них загін, який складається з одного офіцера, двох сержантів і 20 рядових? Така ж задача, якщо в загін повинен увійти командир роти і старший з сержантів.

Розв’язок. Офіцера можна вибрати способами, сержантів способами і рядових способами. Усього за правилом добутку маємо .

Якщо в загін повинен увійти командир роти і старший із сержантів, то маємо способів вибору.

Завдання 8. Розглянемо слово СТІЛ. Скільки слів із 4 букв можна скласти, якщо букви в словах повторюються?

Розв’язок. Якщо можливі повторення букв, наприклад, СТТЛ, СІСЛ, ТТТТ та ін., тоді одержимо кількість слів .

Завдання 9. Розглянемо слово СТІЛ. Скільки слів із 3 букв можна скласти, якщо букви в словах повторюються?

Розв’язок. Якщо можливі повторення букв, наприклад, СТТ, ССС, ІТІ, ЛЛТ та ін., тоді одержимо кількість слів .

Завдання 10. Скільки різних слів можна одержати, переставляючи літери слова «МАТЕМАТИКА»?

Розв’язок. Слово «МАТЕМАТИКА» містить 3 літери «А» , 2 літери «М» , 2 літери «Т»( і по одній літері «Е» , «И» , «К» .

Різні слова з цих літер являють собою перестановки цих літер зі специфікацією .

Кількість таких перестановок дорівнює

.

Завдання 11. У кондитерській є тістечка 4 сортів. Якою кількістю способів можна купити 7 тістечок?

Розв’язок. Порядок, у якому купуються тістечка, ролі не відіграє. Важливо лише, скільки тістечок кожного сорту в покупці. Тому покупку варто розглядати як сполучення з 4 по 7 з повтореннями. Кількість різних покупок дорівнює .

Завдання 12. Записати усі композиції числа 3.

Розв’язок. Композиції мають вигляд 3=3, 3=2+1, 3=1+2, 3=1+1+1.

Завдання 13. Обчислити за допомогою бінома Ньютона вираз .

Розв’язок. Використаємо загальну формулу бінома Ньютона . Нехай , , . Тоді

.

.

Завдання 14. Розкрити за поліноміальною формулою .

Розв’язок. Число доданків після розкриття дужок і приведення подібних дорівнюватиме ,

.

Завдання 15. Група студентів проходила практику в Німеччині та Франції. Половина студентів проходила практику у Франції. В обох країнах навчались 12 студентів, 39 студентів навчались у Німеччині. Скільки студентів в групі, якщо усі пройшли практику?

Розв’язок. В цьому випадку є дві властивості ( – навчання в Німеччині, – навчання у Франції). Використовується загальна формула включення і виключення

,

де – загальна кількість студентів, ;

– кількість студентів, які проходили практику у Франції, ; – кількість студентів, які проходили практику у Німеччині, ; – кількість студентів, які проходили практику в обох країнах, ;

– кількість студентів, які не проходили практику, .

Складемо рівняння: . Розв’язавши його, отримаємо загальну кількість студентів, яка дорівнює 54.

Завдання 16. Маємо деяку кількість куль, кожна з яких пофарбована одним, двома чи трьома кольорами: червоним, синім і жовтим. При цьому червоним пофарбовано 28 куль, синім – 23, жовтим – 23, червоним і синім – 12, синім і жовтим – 8, червоним і жовтим – 11, а всіма трьома – 5 куль. Скільки разом було пофарбовано куль?

Розв’язок. Нехай – властивість кулі: у розфарбуванні кулі бере участь червоний колір, – властивість кулі: у розфарбуванні кулі бере участь синій колір, – властивість кулі: у розфарбуванні кулі бере участь жовтий колір. Тоді умови задачі можна записати так: ; ; ; ; ; ; . тому, що всі кулі пофарбовані.

Формула включення і виключення дає

.

Тоді .

Завдання 17. Задача про безладдя.

Задано різних предметів та різних кліток . Скількома способами можна розмістити предмети по клітках так, щоб жоден предмет не потрапив у клітку ?

Розв’язок. Як початкову множину візьмемо сукупність усіляких розміщень предметів по клітках. Тоді . Введемо властивості : « знаходиться в клітці », . Число розміщень, при якому предмет знаходиться в клітці , дорівнює . Однак тоді .

Використовуючи формулу включень і виключень, знаходимо, що кількість розміщень, при якому жодна з властивостей не виконується (тобто жоден із предметів не потрапив у клітку ), становить

.

Завдання 18. Скільки цілих додатних чисел у першій сотні не ділиться ні на одне із чисел 2, 3, 5?

Розв’язок. Введемо наступні позначення для властивостей: – число ділиться на 2; – число ділиться на 3; – число ділиться на 5.

За умови задачі:

.

Тоді число цілих чисел, яке не ділиться ні на одне із чисел 2, 3, 5, можна знайти, використовуючи формулу включень і виключень

.

Завдання 10.

Поясніть, які з орієнтованих графів, зображених на рис. 4.10, мають ейлерів цикл?

Рисунок 4.10

Завдання 11.

Найдіть гамільтонів цикл, якщо він існує, для кожного з графів, які зображені на рис. 4.11.

Рисунок 4.11

Завдання 12.

Нарисуйте такі графи: а) ; б) ; в) ; г) .

4.4 Приклади аудиторних і домашніх завдань

Завдання 1. Визначити, чи є для графа , зображеного на рис. 4.1, відповідний маршрут колом, простим колом, циклом, простим циклом, якщо маршрут заданий як: 1) ; 2) ; 3) ; 4) ; 5) .

Розв’язок. Відповідно до визначення кола, простого кола, циклу, простого циклу одержимо: 1) простий цикл (усі вершини й ребра різні); 2) цикл (усі ребра різні, а вершини ні); 3) просте коло; 4) маршрут (є однакові ребра й вершини); 5) просте коло.

Завдання 2. Визначити число компонент зв’язності в графі , якщо граф задається так (рис. 4.12)

Рисунок 4.12 – Граф , для якого визначається число компонент зв’язності

Розв’язок. Граф має дві компоненти зв’язності, в першу входять вершини , в другу - .

Завдання 3. Розкласти орграф , зображений на рис. 4.13, на сильно зв’язані компоненти.

Рисунок 4.13

Розв’язок. Граф розкладається на три сильно зв’язані компоненти , , (рис. 4.14)

Рисунок 4.14

Завдання 4.

Знайти в графі , зображеному на рис. 4.15, всі точки зчленування і мости.

Рисунок 4.15

Розв’язок.

Послідовно розглянемо ребра графа, вилучаючи їх із графа. Тільки вилучення ребра призводить до збільшення числа компонент зв’язності, тому є мостом. Аналогічно розглядаємо вершини графа і знаходимо, що вершини 3 і 5 є точками зчленування, тому що вилучення їх із графа призводить до збільшення числа компонент зв’язності.

Завдання 5.

Знайти такі метричні характеристики графа (рис. 4.16): ексцентриситети усіх вершин графа, діаметр графа, радіус графа, периферійні вершини графа, діаметральні кола, центральні вершини графа, центр графа.

Рисунок 4.16

Розв’язок.

Ексцентриситетом вершини є відстань від до найбільш віддаленої від неї вершини, тому , , . Максимальний з усіх ексцентриситетів є діаметром графа, тобто . Найменший з ексцентриситетів є радіусом графа, тобто . Вершина є периферійною, якщо її ексцентриситет дорівнює діаметру графа, тобто , тому периферійними вершинами графа є вершини і . Просте коло, відстань між кінцями якого дорівнює , називається діаметральним колом ом, тому діаметральними ланцюгами графа є такі ланцюги: і . Вершина називається центральною вершиною графа, якщо на ній досягається мінімум ексцентриситетів, тобто , тому центральною вершиною графа є вершина . Множина усіх центральних вершин графа є центром графа, тому центром графа є .

Завдання 6.

Визначити, чи є граф , зображений на рис. 4.17, ейлеровим.

Рисунок 4.17

Розв’язок.

Використаємо теорему Ейлера: граф є ейлеровим (містить ейлерів цикл) тоді і тільки тоді, коли він зв’язний і степені всіх його вершин – парні.

Граф є зв’язним. Степені його вершин такі: , , . Граф не є ейлеровим, тому що не всі степені вершин є парними.

Завдання 7.

Чи має граф, зображений на рис. 4.18, власний ейлерів шлях?

Рисунок 4.18

Розв’язок.

Використаємо таку теорему: граф (мультограф або псевдограф) має власний ейлерів шлях тоді й тільки тоді, коли він зв’язний і рівно дві його вершини мають непарний степінь. Граф, зображений на рис. 4.18, зв’язний, має власний ейлерів шлях, оскільки рівно дві його вершини ( і ) мають непарний степінь, тобто .

Завдання 8.

Чи має орієнтований граф, зображений на рис. 4.19, ейлерів цикл?

Рисунок 4.19

Розв’язок.

Використаємо таку теорему: орієнтований граф має ейлерів цикл тоді й тільки тоді, коли він зв’язний, і півстепені виходу та заходу у вершині рівні. Орієнтований граф, зображений на рис. 4.19, не містить ейлерів цикл, тому що півстепені виходу та заходу у вершинах і не дорівнюють відповідно один одному.

Завдання 9.

Знайдіть гамільтонів цикл, якщо він існує, у графі , що зображений на рис. 4.20.

Рисунок 4.20

Розв’язок.

Гамільтонів цикл для графа буде таким .

Розв’язок.

Усі кореневі дерева з числом вершин зображені на рис. 5.10.

Рисунок 5.10 – Кореневі дерева з вершинами

Завдання 7. Нехай – зв’язний граф з позначеними вершинами. Знайти кількість остовних дерев графа , який зображено на рис. 5.11.

Рисунок 5.11 – Граф

Розв’язок. Для розв’язання завдання використаємо теорему Кірхгофа (матричну формулу Кірхгофа), тобто число остовних дерев у простому зв’язному графі з вершинами () дорівнює алгебраїчному доповненню будь-якого елемента матриці Кірхгофа .

Матриця Кірхгофа складається з таких елементів

Запишемо матрицю Кірхгофа для графа

.

Розрахуємо алгебричне доповнення елемента матриці

.

Існує вісім остовних дерев графа .

Завдання 8. Побудувати остовне дерево у графі , який зображено на рис. 5.12, використовуючи алгоритм пошуку вглиб.

Рисунок 5.12 – Граф

Розв’язок. Для розв’язання завдання використаємо такий алгоритм пошуку остовного дерева вглиб.

Крок 1. Позначити кожну вершину графа символом .

Крок 2. Вибрати довільний елемент графа та назвати його коренем дерева.

Крок 3. Замінити позначку вершини з «нов» на «вик» і назначити .

Крок 4. Поки є вершини, які ще не вибрані, суміжні з , виконати такі дії:

а) вибрати вершину , суміжну з ;

б) якщо має позначку «нов», додати () в множину (множину ребер остовного дерева, яке будується), замінити позначку на «вик», позначити і повторити крок 4;

в) якщо має позначку «вик» і не є «батьком» , додати () в множину (множину зворотних ребер) і повторити крок 4.

Крок 5. Якщо , позначити і повторити крок 4. Поки для вершини є суміжна невикористана вершина , продовжується шлях від до . Тільки в тому випадку, коли рухатися далі не можна, переходимо до кроку 5, повертаємося до «батька» вершини .

Використаємо цей алгоритм для пошуку остовного дерева графа , зображеного на рис. 5.12.

Як корінь довільним способом виберемо вершину . Змінюємо позначку з «нов» на «вик». Оскільки вершина суміжна з і має позначку «нов», додаємо ребро в множину і замінюємо позначку вершини на «вик», як зображено на рис. 5.13, а).

Рисунок 5.13

Від вершини переходимо до вершини , оскільки вона є суміжною з . Вершина має позначку «нов», тому додаємо ребро в множину і заміняємо позначку вершини на «вик», як зображено на рис. 5.13, б).

Тепер вибираємо вершину, яка суміжна з вершиною . Можна вибрати або . Вибір визначає форму дерева, тому пошук углиб не продукує дерево єдиним способом. Припустимо, що наступною вершиною буде вершина . Вершина має позначку «нов», тому додаємо ребро в множину і замінюємо позначку вершини на «вик», як зображено на рис. 5.13, в).
З вершини вибираємо вершину , оскільки вона є суміжною з . Вершина має позначку «нов», тому додаємо ребро в множину і замінюємо позначку вершини

ЧТО ТАКОЕ УВЕРЕННОЕ ПОВЕДЕНИЕ В МЕЖЛИЧНОСТНЫХ ОТНОШЕНИЯХ? Исторически существует три основных модели различий, существующих между...

Что делать, если нет взаимности? А теперь спустимся с небес на землю. Приземлились? Продолжаем разговор...

Живите по правилу: МАЛО ЛИ ЧТО НА СВЕТЕ СУЩЕСТВУЕТ? Я неслучайно подчеркиваю, что место в голове ограничено, а информации вокруг много, и что ваше право...

ЧТО И КАК ПИСАЛИ О МОДЕ В ЖУРНАЛАХ НАЧАЛА XX ВЕКА Первый номер журнала «Аполлон» за 1909 г. начинался, по сути, с программного заявления редакции журнала...

Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте: