- •1. Логіка висловлювань
- •10. Множини. Поняття, приклади
- •13. Відповідності і відношення
- •15. Відношення еквівалентності
- •21. Групи, кільця, поля
- •40. Поняття графа
- •Логіка висловлювань Завдання 1
- •Завдання 2
- •Завдання 11
- •Завдання 12
- •Завдання 13
- •Завдання 14
- •Завдання 10
- •Кодування Завдання 1
- •Завдання 2
- •Завдання 4
- •Список літератури
Завдання 10
Скільки різних трикольорових прапорів можна зробити, маючи 5 кольорів, якщо на кожному прапорі має бути червоний?
Розв’язування:
Місце для червоного кольору можна обрати трьома способами. Після цього залишаться дві вільних смуги. Для першої зверху смуги можна вибрати колір 4 способами. Тоді для останньої смуги залишиться 3 можливих кольори. За правилом множення загальна кількість різних трикольорових прапорів складе
3*4*3 = 36.
Завдання 11
Скількома різними способами можна розмістити п'ять різних книжок на книжковій полиці?
Розв’язування:
Кількість способів, якими п’ять різних книжок можна розмістити на книжковій полиці, дорівнює кількості перестановок з 5 елементів, тобто 5!= 120.
Завдання 12
Скільки тризначних чисел можна скласти з цифр 0, 1, 2, 3, 4, 5, якщо цифри можуть повторюватися?
Розв’язування:
Першу цифру можна вибрати п’ятьма способами, оскільки цифра 0 не може стояти на першому місці. Кожну з двох інших цифр можна вибрати 6 способами.
Тоді за правилом множення шукана кількість тризначних чисел дорівнює
5*6*6 = 180.
Завдання 13
Скільки тризначних чисел можна скласти з цифр 0, 1, 2, 3, 4, 5, якщо ні одна цифра не може повторюватися?
Розв’язування:
Перша цифра тризначного числа не може бути нулем, тому її обрати можна 5 способами.
Друга цифра не може збігатися з першою, тому її можна обрати 5 способами.
Третя цифра не може збігатися з першими двома, тому її можна обрати 4 способами.
Тоді за правилом множення шукана кількість тризначних чисел дорівнює
5*5*4 = 100.
Завдання 14
Скількома
способами можна упорядкувати множину
так, щоб останні два елементи були
і
?
Розв’язування:
За
умовою треба впорядкувати
елементи. Тому шукана кількість способів
дорівнює кількості перестановок з
елементів, тобто
Графи
Задано граф G = (X,U), вершини і ребра (дуги) якого пронумеровані числами натурального ряду.
Побудувати:
Матриці суміжності і інцидентності для орієнтованого та неорієнтованого графів.
Матрицю ланцюгів для неорієнтованого графу та матрицю шляхів для орієнтованого графу.
Матрицю циклів неорієнтованого графу та матрицю контурів орієнтованого графу.
Знайти всі можливі шляхи з 1 в 4.
Знайти мінімальний шлях за алгоритмом Дейкстри.
Перемалювати в неорієнтований граф та знайти мінімальне остовне дерево.
Знайти гамільтонів шлях, якщо він існує.
Розв’язування:
1. Матриця суміжності показує, які вершини з’єднані ребрами або дугами.
Матриця суміжності для орієнтованого графа:
.
Матриця суміжності для неорієнтованого графа:
.
Матриця інцидентності показує інцидентність вершин і ребер.
Матриця інцидентності для орієнтованого графа:
.
Матриця інцидентності для неорієнтованого графа:
.
2. Матриця ланцюгів для неорієнтованого графа показує, чи існує ланцюг між вершинами:
Матриця шляхів для орієнтованого графу показує, чи існує шлях з однієї вершини до іншої:
3. Знайдемо всі прості цикли неорієнтованого графа. Запишемо кожен цикл послідовністю вершин:
Z1 = {1,2,3,1}, Z2 = {1,2,4,1}, Z3 = {1,2,5,3,1}, Z4 = {1,2,5,4,1},
Z5 = {1,3,2,4,1}, Z6 = {1,3,5,4,1}, Z7 = {1,2,3,5,4,1}, Z8 = {1,2,4,5,3,1},
Z9 = {1,3,2,5,4,1}, Z10 = {1,3,5,2,4,1}, Z11 = {2,3,5,2}, Z12 = {2,4,5,2},
Z13 = {2,3,5,4,2}.
Складемо матрицю циклів неорієнтованого графу, де простим циклам відповідають рядки, а стовпчикам відповідають ребра.
Знайдемо всі контури орієнтованого графа. Запишемо кожен контур послідовністю вершин:
Z1 = {1, 2, 5, 3, 1}, Z2 = {2, 5, 3, 2}.
Складемо матрицю контурів орієнтованого графу, де контурам відповідають рядки, а стовпчикам відповідають ребра.
4. Знайдемо всі можливі шляхи з 1 в 4. Одержимо три можливих шляхи, запишемо їх послідовністю вершин:
1-4, 1-2-4, 1-2-5-4.
5. Знайдемо мінімальний шлях за алгоритмом Дейкстри з вершини 1 до вершини 4. Вагами ребер будемо вважати їх номери.
Етап 0. Призначаємо вершині 1 постійну позначку [0, –].
Етап 1. З вершини 1 можна досягти вершин 2 і 4. Обчислюємо позначки для цих вершин, в результаті одержимо таку таблицю позначок.
Вершина |
Позначка |
Статус |
1 |
[0, –] |
постійна |
2 |
[0+1, 1] = [1, 1] |
тимчасова |
4 |
[0+9, 1] = [9, 1] |
тимчасова |
Серед вершин 2 і 4 вершина 2 має найменше значення відстані, тому статус позначки цієї вершини змінюється на постійний.
Етап 2. З вершини 2 (останньої вершини з постійною позначкою) можна потрапити в вершини 4 і 5. Отримаємо такий список вершин:
Вершина |
Позначка |
Статус |
1 |
[0, –] |
постійна |
2 |
[0+1, 1] = [1, 1] |
постійна |
4 |
[1+2, 2] = [3, 2] |
тимчасова |
5 |
[1+8, 2] = [9, 2] |
тимчасова |
Статус позначки вершини 4 змінюємо на постійний.
Вершина |
Позначка |
Статус |
1 |
[0, –] |
постійна |
2 |
[0+1, 1] = [1, 1] |
постійна |
4 |
[1+2, 2] = [3, 2] |
постійна |
5 |
[1+8, 2] = [9, 2] |
тимчасова |
Найкоротший шлях визначаємо, використовуючи позначки, починаючи з вершини 4. Одержимо такий найкоротший шлях довжиною 3:
1-2-4.
6. Перемалюємо граф в неорієнтований граф.
Знайдемо мінімальне остовне дерево, використовуючи алгоритм Прима. Спочатку виберемо вершину 1.
На кожному кроці до поточного дерева додається найлегше ребро, яке з’єднує вершину з побудованого дерева, і вершину не з дерева.
З вершини 1 виходять три ребра. Найменшу вагу має 1-2, тому додамо ребро 2. Отже, дерево Х={1-2}.
З цих двох вершин виходять п’ять ребер, найменшу вагу з них має 2-4. Тому додамо це ребро: Х={1-2, 2-4}.
Перелік ребер, з яких треба вибрати найлегше ребро:
1-3 (6), 2-3 (7), 2-5 (8), 4-5 (4).
Отже, додаємо ребро 4-5: Х={1-2, 2-4, 4-5}.
Перелік ребер, з яких треба вибрати найлегше ребро:
1-3 (6), 2-3 (7), 5-3 (5).
Отже, додаємо ребро 5-3:
Х={1-2, 2-4, 4-5, 5-3}.
Всі вершини знаходяться в дереві. Робота алгоритму завершено. Маємо такий найкоротший остов.
Підсумкова довжина буде дорівнювати
1+2+4+5 = 12.
7. Шлях 1, 2, 4, 5, 3 буде гамільтоновим.
