ГРАФИ
Останнім часом графи і пов'язані з ними методи досліджень органічно пронизують на різних рівнях чи не всю сучасну математику. Теорія графів розглядається як одна з гілок топології; безпосереднє відношення вона має також до алгебри і до теорії чисел. Графи ефективно використовуються в теорії планування та управління, теорії розкладів, соціології, математичній лінгвістиці, економіці, біології, медицині, географії. Широке застосування знаходять графи в таких областях, як програмування, теорія кінцевих автоматів, електроніка, в рішенні імовірнісних і комбінаторних задач, знаходженні максимального потоку в мережі, найкоротшої відстані, максимального паросполучення, перевірки планарності графа і ін. Як особливий клас можна виділити задачі оптимізації на графах. Математичні розваги і головоломки теж є частиною теорії графів, наприклад, знаменита проблема чотирьох фарб, інтригуюча математиків і по сей день. Теорія графів швидко розвивається, знаходить все нові додатки і чекає молодих дослідників.
Розглянемо такі три
завдання:
1. Хто грає Ляпкина-Тяпкіна? У шкільному драмгуртку вирішили ставити
гоголівського «Ревізора». І тут розгорілася запекла суперечка. Все почалося з
Ляпкина-Тяпкіна.
- Ляпкіним-Тяпкіним буду я! - Рішуче заявив
Гена.
- Ні, я буду Ляпкіним-Тяпкіним, - заперечив Діма.- З
раннього дитинства мріяв втілити цей образ на сцені.
- Ну, добре, згоден поступитися цією
роллю, якщо мені дадуть зіграти Хлестакова, - проявив великодушність Гена.
- ... А мені - Осипа, - не поступився йому у великодушності Діма.
- Хочу бути Зємлянікою або Городничим, - сказав
Вова.
- Ні, Городничим буду я, - хором
закричали Алік і Боря. - Або Хлестаковим, - додали вони одночасно.
Чи вдасться розподілити ролі так, щоб
виконавці були задоволені? (Ми не запитуємо, чи будуть задоволені глядачі.)
2. Сварливі сусіди. Жителі п'яти будинків посварилися один з одним (див.рис.) і, щоб не зустрічатися біля криниць, вирішили поділити їх (криниці) так, щоб господар кожного
дому ходив до «своєї» криниці по «своїй» стежці. Чи вдасться їм це зробити?
3. Кошики, повні яблук. У п'яти кошиках лежать яблука п'яти
різних сортів (див.рис.). Яблука першого сорту лежать в кошиках Г і Д, яблука другого сорту - в
кошиках А, Б і Г, кошиках А, Б і В є яблука п'ятого сорту, в кошику В є до
того ж яблука четвертого сорту, а в кошику Д - третього. Необхідно дати кожній корзині номер, але так, щоб в кошику
№ 1 були яблука першого сорту (хоча б одне), в кошику № 2 - другого і т. д.
Обговорення. Ці завдання досить
прості. Гідно подиву інше - хоча на перший погляд ці завдання досить різні - в
одній йдеться про розподіл ролей, в іншій - про стежки від будинків до криниць, у
третій - про нумерацію кошиків з яблуками, існує єдиний підхід до їх вирішення,
пов'язаний з так званою теоріею графів.
Перевівши ці завдання на мову теорії
графів, ви побачите, що всі три завдання перетворяться в одну простеньку задачу
«на графи», розв’язавши яку
ви тим самим розв’яжете
всі три поставлені вище завдання.