Page 208 - 4496

Теорія графів відноситься до області дискретної
математики і займається вивченням геометричних зв'язків між
об'єктами. Основним об'єктом теорії є граф, проте при рішенні
багатьох задач в XX столітті широко стали застосовуватися
інші терміни: карта, мережа, комплекс, діаграма, лабіринт.
Теорія графів тісно пов'язана з різними розділами математики:
топологією, алгеброю, теорією ймовірності, теорією чисел і,
звичайно, з комбінаторикою.
Приведемо деякі приклади задач теорії графів, які
розв'язуються комбінаторними методами.
1 Є n учасників шахового турніру. Скільки партій
повинно бути зіграно, щоб кожний учасник зіграв зі всіма
іншими? Будь-який турнір між n учасниками (командами)
може бути представлений у вигляді графа, при цьому після
закінчення турніру граф повинен бути повним. Кожний
учасник (вершина графа) грає зі всіма іншими (їх число n - 1),
а оскільки число учасників рівне n, то всього ігор n(n – 1)/2.
2 Комбінаторні задачі сортування часто зображаються у
вигляді графів типу "дерево".
3 Не вирішена аналітично задача Гамільтона про обхід
всіх вершин зв'язного графа в точності по одному разу для
визначення числа кроків впорядкованого перебору
використовує комбінаторні оцінки.

КОНТРОЛЬНЫ ЗАВДАННЯ

1 Скількома способами можна скласти триколірний
смугастий прапор, якщо є матеріал п'яти різних кольорів.
2 Скількома способами можна скласти триколірний
смугастий прапор, якщо є матеріал п'яти різних кольорів й
одна зі смуг прапора повинна бути червоною.
3 Скільки різних слів можна одержати, переставляючи
букви в словах «математика», «інженер».
4 У цеху є дев'ять робочих місць, з яких на двох можуть
працювати тільки жінки, на трьох тільки чоловіка й на
чотирьох – чоловіки й жінки. Скількома способами можна
розподілити трьох жінок і чотирьох чоловіків на робочих
місцях?

205