![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Способи задання графа ⇐ ПредыдущаяСтр 6 из 6
2. Граф можна задати через відображення, визначивши множину його вершин та множину відображень кожної із вершин:
3. Граф можна задати через К -список (підмножину декартового добутку множини вершин графа самої на себе).
4. Найбільш математичним способом задання графа вважають його задання через матрицю суміжності чи матрицю інцидентності. Матрицею суміжності, відповідною до заданного графа, називають квадратну матрицю, розмірність якої дорівнює кількості його вершин, а елементами якої є числа 0 або 1. Причому елемент матриці Матрицею інцидентності, відповідної до заданого графа, називають прямокутну матрицю, кількість рядків якої дорівнює кількості вершин графа, а кількість стовпців – кількості його дуг. Елементами матриці є числа 0, 1 і -1, причому елемент матриці Для того, щоб дати характеристику графа (незалежно від способу його задання) необхідно вказати: – множину вершин даного графа; – ізольовані вершини, вершини входу та виходу (якщо вони існують); – тип графа (щодо орієнтованості); – вказати чи заданий граф є повним; – вказати чи заданий граф є зв’язним;
Наведемо деякі основні задачі в теорії графів.
1. Знаходження найкоротшого шляху у графі. Нехай у заданому графі необхідно знайти найкоротший шлях із усіх можливих, що з’єднують вершину Спершу вершині
2. Знаходження оптимального шляху у зваженому графі (шляху мінімальної ваги). Нехай у заданому зваженому графі необхідно знайти шлях найменшої ваги з усіх можливих, що з’єднують вершину Спершу проводимо початкову індексацію вершин: вершині Якщо індекс вершини
3. Знаходження числа шляхів або контурів заданої довжини. Нехай необхідно знайти кількість шляхів довжини k, що з’єднують вершини У випадку, коли необхідно знайти кількість контурів, діємо аналогічним чином, враховуючи означення контура, – результат буде міститися на головній діагоналі результуючої матриці. Сума діагональних елементів становить число всіх контурів потрібної довжини у заданому графі.
Наведемо декілька прикладів розв'язування задач із теорії графів. Приклад 1. Охарактеризувати граф, заданий матрицею суміжності
Розв’язування. Скористаємося планом характеристики графа, що поданий у теоретичній частині. 1. Множина вершин даного графа 2. Вершина h є ізольованою, оскільки в матриці суміжності цій вершині відповідають нульовий рядок і стовпець. Вершинами входу є вершини 3. Оскільки матриця суміжності несиметрична – граф є графом змішаного типу. Існують строго напрямлені дуги такі як 4. Оскільки у графі є ізольована вершина, то граф не є повним і не є зв’язним.
Приклад 2. Граф, що заданий у попередньому завданні записати через відповідні множини відображень. Розв’язування. Множина вершин даного графа Запишемо множину відображень для кожної вершини графа:
Приклад 3. Знайти кількість контурів довжини 3 з вершини a та кількість шляхів довжини 2, що з’єднують вершини c та b у підграфі графа, який заданий у попередньому завданні з вершинами Розв’язування. Для знаходження кількості шляхів довжини 2, що з’єднують вершини c та b необхідно матрицю суміжності
Квадрат матриці суміжності заданого графа є матрицею вигляду
Кількість шляхів довжини 2, що з’єднують вершини c та b визначає елемент Для визначення кількості контурів довжини 3 з вершини a необхідно знайти елемент Завдання для самостійної роботи
Завдання з розділу „Теорія множин” 1. Дано
2. Задано множини:
Знайти результат виконання операцій над множинами.
3. Задано множини:
4. Використовуючи операції над множинами, розв'язати задачу:
4.1. Кожен учень у класі вивчає англійську або французьку мову. Тільки англійську мову вивчають 7 учнів, тільки французьку – 5, а 16 учнів вивчають обидві мови. Скільки учнів у класі? 4.2. У класі 30 учнів. Кожен із них займається футболом або хокеєм. Третина учнів класу займається тільки хокеєм, а 5 учнів і хокеєм, і футболом. Скільки учнів займаються футболом? 4.3. У класі 35 учнів. Кожен учень у класі вивчає англійську або німецьку мову. Англійську мову вивчають 17 учнів, а німецьку – 25. Скільки учнів у класі вивчають і англійську, і німецьку мови? 4.4. У класі 20 учнів. Кожен із них відвідує факультативні заняття з математики, фізики чи хімії. 5 учнів класу відвідують лише математичний факультатив, фізикою займаються 8 учнів, а хімією –12. Скільки учнів класу відвідують більше, ніж один факультатив? 4.5. У класі 40 учнів. Кожен із них займається футболом чи хокеєм. Половина учнів класу займається тільки хокеєм, а 10 учнів – тільки футболом. Скільки учнів класу займаються і хокеєм, і футболом? 4.6. У групі з 20 дітей половина захоплюється малюванням, а інші музикою або танцями. Тільки музикою захоплюється 4 дітей, 3 дітей захоплюються і музикою, і танцями. Скільки дітей захоплюється танцями? 4.7. У класі 33 учні. На домашнє завдання слід було виконати 5 вправ. Усі учні виконали хоча б 3 вправи. 10 учнів виконали домашнє завдання повністю. Скільки учнів класу виконали лише 4 вправи? 4.8. На домашнє завдання слід було виконати 2 вправи. 10 учнів виконали першу вправу, 12 учнів зробили лише друге завдання. 2 учнів виконали домашнє задання повністю. Скільки учнів у класі? 4.9. У дитячому садку вивчали вірші та приказки. 10 дітей вивчили вірш, а 15 вивчили приказку, 5 дітей вивчили і вірш, і приказку. Скільки дітей у групі дитсадка? 4.10. У класі 20 учнів. На домашнє завдання потрібно було вивчити вірша чи прислів’я. Половина дітей вивчили вірш, а 7 вивчили і вірш, і прислів’я. Скільки дітей вивчили прислів’я? 4.11. Кожен учень у класі вивчає англійську або французьку мову. Лише англійську мову вивчають 7 учнів, лише французьку – 5, а 16 вивчають обидві мови. Скільки учнів у класі? 4.12. У класі 30 учнів. Кожен з них займається футболом чи хокеєм. Третина учнів класу займається тільки хокеєм, а 5 учнів і хокеєм, і футболом. Скільки учнів займаються футболом? 4.13. У класі 35 учнів. Кожен учень у класі вивчає англійську або німецьку мову. Англійську мову вивчають 17 учнів, а німецьку – 25. Скільки учнів у класі вивчають і англійську, і німецьку мови? 4.14. У класі 20 учнів. Кожен з них відвідує факультативні заняття з математики, фізики чи хімії. 5 учнів класу відвідують лише математичний факультатив, фізикою займаються 8 учнів, а хімією –12. Скільки учнів класу відвідують більше, ніж один факультатив? 4.15. У класі 40 учнів. Кожен з них займається футболом чи хокеєм. Половина учнів класу займається тільки хокеєм, а 10 учнів – тільки футболом. Скільки учнів класу займаються і хокеєм, і футболом? 4.16. У групі з 20 дітей половина захоплюється малюванням, а інші музикою або танцями. Тільки музикою захоплюється 4 дітей, 3 дітей захоплюються і музикою, і танцями. Скільки дітей захоплюється танцями? 4.17. У класі 33 учні. На домашнє завдання слід було виконати 5 вправ. Усі учні виконали хоча б 3 вправи. 10 учнів виконали домашнє завдання повністю. Скільки учнів класу виконали лише 4 вправи? 4.18. На домашнє завдання слід було виконати 2 вправи. 10 учнів виконали першу вправу, 12 учнів зробили лише друге завдання. 2 учнів виконали домашнє завдання повністю. Скільки учнів у класі? 4.19. У дитячому садку вивчали вірші та приказки. 10 дітей вивчили вірш, а 15 вивчили приказку, 5 дітей вивчили і вірш, і приказку. Скільки дітей у групі? 4.20. У класі 20 учнів. На домашнє завдання потрібно було вивчити вірша чи прислів’я. Половина дітей вивчили вірш, а 7 вивчили і вірш, і прислів’я. Скільки дітей вивчили прислів’я? 4.21. Кожен учень у класі вивчає англійську або французьку мову. Лише англійську мову вивчають 7 учнів, лише французьку – 5, а 16 вивчають обидві мови. Скільки учнів у класі? 4.22. У класі 30 учнів. Кожен з них займається футболом чи хокеєм. Третина учнів класу займається тільки хокеєм, а 5 учнів і хокеєм, і футболом. Скільки учнів займаються футболом? 4.23. У класі 35 учнів. Кожен учень у класі вивчає англійську або німецьку мову. Англійську мову вивчають 17 учнів, а німецьку – 25. Скільки учнів у класі вивчають і англійську, і німецьку мови? 4.24. У класі 20 учнів. Кожен з них відвідує факультативні заняття з математики, фізики чи хімії. 5 учнів класу відвідують лише математичний факультатив, фізикою займаються 8 учнів, а хімією – 12. Скільки учнів класу відвідують більше, ніж один факультатив? 4.25. У класі 40 учнів. Кожен з них займається футболом чи хокеєм. Половина учнів класу займається тільки хокеєм, а 10 учнів – тільки футболом. Скільки учнів класу займаються і хокеєм, і футболом? 4.26. У групі з 20 дітей половина захоплюється малюванням, а інші музикою або танцями. Тільки музикою захоплюється 4 дітей, 3 дітей захоплюються і музикою, і танцями. Скільки дітей захоплюється танцями? 4.27. У класі 33 учні. На домашнє завдання слід було виконати 5 вправ. Усі учні виконали хоча б 3 вправи. 10 учнів виконали домашнє завдання повністю. Скільки учнів класу виконали лише 4 вправи? 4.28. На домашнє завдання слід було виконати 2 вправи. 10 учнів виконали першу вправу, 12 учнів зробили лише друге завдання. 2 учнів виконали домашнє завдання повністю. Скільки учнів у класі? 4.29. У дитячому садку вивчали вірші та приказки. 10 дітей вивчили вірш, а 15 вивчили приказку, 5 дітей вивчили і вірш, і приказку. Скільки дітей у групі? 4.30. У класі 20 учнів. На домашнє завдання потрібно було вивчити вірша чи прислів’я. Половина дітей вивчили вірш, а 7 вивчили і вірш, і прислів’я. Скільки дітей вивчили прислів’я? Завдання з розділу „Комбінаторика”
5. Розв’язати задачу та пояснити хід розв’язання. 5.1. Скільки різних послідовностей можна утворити з 6-ти одиниць та 10-ти нулів? 5.2. Скільки різних шестисимвольних кодів можна утворити на множині літер української абетки? 5.3. Скількома різними способами можна поставити в два ряди семеро осіб для виконання їх групового портрету? 5.4. У повному комплекті гри в доміно – 28 кісточок. Скільки кісточок буде мати повний комплект дитячого доміно, якщо замість цифр використати 9 різних малюнків? 5.5. Скількома способами можна розселити 12 студентів у 4 тримісні кімнати гуртожитку? 5.6. Скількома способами можна розділити групу з 24 студентів на дві рівні підгрупи для здачі модульного контролю? 5.7. Скількома способами можна розділити групу з 24 студентів на три рівні підгрупи для здачі нормативів з фізкультури? 5.8. Із 19 запитань потрібно скласти екзаменаційні білети, причому в кожен білет вписується лише два запитання. Скільки таких білетів можна скласти? 5.9. Десять нових працівників необхідно розподілити на робочі місця. Існує 6 відділів, причому кожен зі співробітників може працювати у будь-якому відділі. Скількома способами можна зробити призначення? 5.10. У дитячий садок надійшло 5 нових дітей, яких треба розподілити в 7 груп, причому в одну групу не більше однієї дитини. Скільки можливостей розподілу по групах в цьому випадку існує? 5.11. Скільки різних послідовностей можна утворити з 4-ох одиниць та 12-ти нулів? 5.12. Скільки різних семисимвольних кодів можна утворити на множині літер латинської абетки? 5.13. Скількома різними способами можна поставити в два ряди 6 осіб для виконання їх групового портрету? 5.14. У повному комплекті гри в доміно – 28 кісточок. Скільки кісточок буде мати повний комплект дитячого доміно, якщо замість цифр використати 5 різних малюнків? 5.15. Скількома способами можна розселити 12 студентів у 3 чотиримісні кімнати гуртожитку? 5.16. Скількома способами можна розділити групу з 20 студентів на дві рівні підгрупи для здачі модульного контролю? 5.17. Скількома способами можна розділити групу з 21 студентів на три рівні підгрупи для здачі нормативів з фізкультури? 5.18. Із 26 запитань потрібно скласти екзаменаційні білети, причому в кожен білет вписується лише два запитання. Скільки таких білетів можна скласти? 5.19. Десять нових працівників необхідно розподілити на робочі місця. Існує 5 відділів, причому кожен зі співробітників може працювати у будь-якому відділі. Скількома способами можна зробити призначення? 5.20. У дитячий садок надійшло 6 нових дітей, яких треба розділити в 7 груп, причому в одну групу не більше однієї дитини. Скільки можливостей розподілу по групах в цьому випадку існує? 5.21. Скільки різних послідовностей можна утворити з 8-ми одиниць та 8-ми нулів? 5.22. Скількома способами за круглим столом можемо розсадити 10 гостей так, щоб певна пара сиділа поруч? 5.23. Скільки різних п’ятисимвольних кодів можна утворити на множині десяти арабських цифр абетки? 5.24. Скількома різними способами можна поставити в ряд семеро і восьмеро хлопців, щоб дівчата не стояли на груповому портреті поруч? 5.25. Скількома способами можна розселити 9 студентів у 3 тримісні кімнати гуртожитку? 5.26. Скількома способами можна розділити групу з 26 студентів на дві рівні підгрупи для здачі модульного контролю? 5.27. Скількома способами можна розділити групу з 24 студентів на чотири рівні підгрупи для здачі нормативів з фізкультури? 5.28. Скільки різних двійкових чисел можна утворити з 6-ти одиниць та 10-ти нулів, щоб у старшому розряді була одиничка? 5.29. Вісім нових працівників необхідно розподілити на робочі місця. Існує 6 відділів, причому кожен зі співробітників може працювати у будь-якому відділі. Скількома способами можна зробити призначення? 5.30. У дитячий садок надійшло 5 нових дітей, яких треба розділити в 7 груп, причому в одну групу не більше однієї дитини. Скільки можливостей розподілу по групах в цьому випадку існує?
6. Задано множину 6.1. Скільки існує різних перестановок із елементів цієї множини. 6.2. Скільки існує розміщень із елементів цієї множини по 5 елементів, що містять число 11. 6.3. Скільки існує розміщень із елементів цієї множини по 5 елементів, що містять числа 11 і 13. 6.4. Скільки існує розміщень із елементів цієї множини по 5 елементів, що містять число 11 або 13. 6.5. Скільки існує розміщень із елементів цієї множини по 4 елементи, що містять числа 1 і 2 або 17. 6.6. Скільки існує розміщень із елементів цієї множини по 4 елементи, що містять числа 1 і 17. 6.7. Скільки існує різних перестановок із підмножини елементів цієї множини, які мають парні індекси. 6.8. Скільки існує різних перестановок із підмножини елементів цієї множини, які мають непарні індекси. 6.9. Скільки існує різних перестановок із підмножини елементів цієї множини, які мають індекси кратні 3. 6.10. Скільки існує розміщень із елементів цієї множини по 5 елементів, що містять число 13. 6.11. Скільки різних намист можна укласти з 10 намистин різного розміру. 6.12. Скількома способами можна вибрати 3 однакові карти з 6.13. Скількома способами можна вибрати 5 послідовно занумерованих карт з колоди 6.14. Скількома способами можна вибрати 5 карт з колоди 6.15. Скількома способами можна вибрати 5 послідовно занумерованих карт однієї масті з колоди 6.16. Скількома способами можна вибрати 5 карт з колоди 6.17. Скількома способами можна приставити дві кісточки одна до одної з набору 28 доміно так, щоб суміжні поля обидвох співпадали. 6.18. Скільки різних намист можна укласти з 20 намистин різного розміру. 6.19. Скількома способами можна вибрати 5 карт з колоди 6.20. Скільки різних намист можна укласти з 10 намистин, серед яких 8 намистин одного типорозміру, а ще дві є дещо більшими.
Задано множину 6.21. Скільки існує різних перестановок із елементів цієї множини. 6.22. Скільки існує розміщень із елементів цієї множини по 5 елементів, що містять число 12. 6.23. Скільки існує розміщень із елементів цієї множини по 5 елементів, що містять числа 12 і 14. 6.24. Скільки існує розміщень із елементів цієї множини по 5 елементів, що містять число 12 або 14. 6.25. Скільки існує розміщень із елементів цієї множини по 4 елементів, що містять числа 2, 4, 16. 6.26. Скільки існує розміщень із елементів цієї множини по 4 елементів, що містять числа 2 і 16. 6.27. Скільки існує різних перестановок із підмножини елементів цієї множини, які мають парні індекси. 6.28. Скільки існує різних перестановок із підмножини елементів цієї множини, які мають непарні індекси. 6.29. Скільки існує різних перестановок із підмножини елементів цієї множини, які мають індекси кратні 3. 6.30. Скільки існує розміщень із елементів цієї множини по 5 елементів, що містять число 14.
7. Виконати завдання. Довести тотожність. 7.1. 7.2. 7.3. 7.4. 7.5. 7.6. 7.7. 7.8. 7.9. 7.10.
Обчислити коефіцієнти многочлена: 7.11. 7.12. 7.13. Обчислити значення коефіцієнта при степені у многочлені: 7.14. 7.15. 7.16. Скільки є членів у вказаному виразі? 7.17. 7.18. 7.19. 7.20. Розв'язазати рекурентне рівняння. 7.21. 7.22. 7.23. 7.24. 7.25. 7.26. 7.27. 7.28. 7.29. 7.30. Завдання з розділу „Математична логіка” 8. Побудувати таблиці істинності формул 8.1 8.2 8.3 8.4 8.5 8.6 8.7 8.8 8.9 8.10 8.11 8.12 8.13 8.14 8.15 8.16 8.17 8.18 8.19 8.20 8.21 8.22 8.23 8.24 8.25 8.26 8.27 8.28 8.29 8.30
9. Побудувати еквівалентні формули в алгебрі Буля.
9.1. 9.2. 9.3. 9.4. 9.5. 9.6. 9.7. 9.8. 9.9. 9.10. 9.11. 9.12. 9.13. 9.14. 9.15. 9.16. 9.17. 9.18. 9.19. 9.20. 9.21. 9.22. 9.23. 9.24. 9.25. 9.26. 9.27. 9.28. 9.29. 9.30.
10. Побудувати еквівалентні формули в алгебрі Жегалкіна.
10.1. 10.2. 10.3. 10.4. 10.5. 10.6. 10.7. 10.8. 10.9. 10.10. 10.11. 10.12. 10.13. 10.14. 10.15. 10.16. 10.17. 10.18. 10.19. 10.20. 10.21. 10.22. 10.23. 10.24. 10.25. 10.26. 10.27. 10.28. 10.29. 10.30. (У поданих нижче завданнях номер варіанту — цифра молодшого розряду спискового номера)
11. Для заданої формули алгебри логіки побудувати відповідні їй досконалу диз’юнктивну та досконалу кон’юнктивну нормальні форми, як за таблицею істинності, так і аналітично.
12. Для заданої формули алгебри логіки знайти мінімальну диз’юнктивну нормальну форму методами: a) Квайна;
b) Мак-Класкі;
c) Блейка-Порецького.
13. Встановити, до якого класу функцій належить задана булева функція.
|