19.4 Контрольні запитання та завдання

1. Назвіть галузі застосування завдань про транспортні мережі у житті.

2. Що називається мережею?

3. Що таке потік у мережі? Перелічіть основні властивості потоку.

4. Як визначається розмір потоку?

5. Сформулюйте теорему Форда-Фалкерсона.

6. Опишіть алгоритм знаходження максимального потоку у мережі.

7. У якому випадку потік є максимальним?

8. Яким властивостям має задовольняти потік у мережі?

9. Чому дорівнює пропускна здатність розрізу?

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

1. Виробник електричних масажних щіток має бажання відправити на певний ринок кілька ящиків своєї продукції. Припустимо, що ці ящики можна відправити декількома різними каналами, показаними нижче на рис. 19.7 (де x_s– виробник, x_t – ринок, а числа, відповідні до чисельника дробу, позначають максимальні вантажі, які можуть бути відправлені відповідними каналами). Виробника цікавить, яку максимальну кількість ящиків він може відправити цією мережею, не перевищуючи припустиму пропускну здатність кожного каналу.

2. На рис. 19.8 розглянута схема електричного ланцюга. Завдання полягає у знаходженні максимального струму, який можна пропустити по цьому ланцюгу за умови, що задано граничні струми окремих проводів.

Рисунок 19.7

Рисунок 19.8

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

4. Доведіть, що якщо кожен юнак зустрічається з k дівчинами, а кожна дівчина – з l юнаками ( ), то задача про весілля має вирішення.

5. Знайти максимальний потік у мережі, яку наведено на рис. 19.9 ( ).

Рисунок 19.9

20 Практичне заняття № 18. Основи комбінаторного аналізу

20.1 Мета заняття

Ознайомитися з загальними правилами та задачами комбінаторики. Набути навичок застосування на практиці правил суми та добутку для розв’язання комбінаторних задач.

20.2 Методичні рекомендації до самостійної роботи студентів

Під час підготовки до практичного заняття необхідно вивчити відповідний розділ конспекту лекцій та ознайомитися з матеріалом підручників [1, c. 413-418; 2, c. 413-418; 10, c. 9-25; 12, c. 262-263; 17, c. 129-153].

При повторенні матеріалу слід звернути увагу на такі питання:

• загальні правила і задачі комбінаторики;

• вибірка;

• правила суми та добутку.

20.3 Приклади розв’язання типових завдань

1. Знайти кількість способів розкладки n різноманітних шпоргалок по m різних кишенях.

Кожна шпоргалка може потрапити в одну з m кишень. Використовуючи правило добутку, маємо m · m … m = mⁿ способів розкладки.

2. Скількома способами студент може добратися до ХНУРЕ, якщо існують такі варіанти: пішки, двома тролейбусами (різних маршрутів), метро чи на таксі?

Виходячи з того, що студент може добратися до ХНУРЕ тільки одним способом, застосовуємо правило суми, за яким кількість способів N визначається як: N = 1+2+1+1 = 5.

3. Написати розкладання бінома Ньютона (12x-8)³.

При n=3 формула бінома Ньютона має вигляд:

;

.

4. Знайти коефіцієнт при a³b.

Згідно з формулою бінома Ньютона, знаходимо: .

5. У місті розташовано 4 технічних ВНЗ, 1 медичний і 2 гуманітарних. Скількома способами можна отримати вищу освіту за державним набором у даному місті?

Оскільки державний набір передбачає безкоштовне навчання тільки в одному ВНЗ, застосуємо правило суми, за яким кількість способів N вибору ВНЗ визначається як: N = 4+1+2 = 7.

6. Є 4 наукові теми, 3 студенти і 2 викладачі. Дослідницька група, яка займається однією темою, складається з одного студента та одного викладача. Скільки існує комбінацій вибору різноманітних тем та різних дослідницьких груп?

Оскільки одна дослідницька група може вести тільки одну тему, використаємо правило добутку, за яким кількість комбінацій дорівнює 4·3·2=24.