Графи та їх застосування

Задача № 2.5. Про кількість тризначних чисел.

Складіть множину тризначних чисел, які можна скласти за допомогою цифр 5 і 2. Скільки таких чисел?

Розв’язання. Будь-яке розташування цифр 5 і 2 в тризначному числі підраховується за допомогою схеми (дерева)(рис. 17), де перший ярус – це розряд сотень, другий – десятків і третій – одиниць.

Відповідь: 222,225,252,255,522,525,552,555. Таких чисел 8.

Задача № 2.5. Задача про шлях.

У туристичному бюро складають маршрути подорожей для автотуристів, яку повинні виїхати з пункту S, відвідати пункти A, B, C, D не більше одного разу кожен, і знову повернутися до пункту S. Пункти і шосейні дороги, що сполучають їх між собою, представлені схемою на рис.18. Числа на рисунку вказують відстань між населеними пунктами по цих дорогах. Допоможіть скласти найекономічніший (найкоротший) шлях для бюро маршрут подорожей.

Розв’язання.  Зверніть увагу, що кожні дві вершини графа шосейних доріг сполучені між собою ребром (рис. 18). Це - повний граф.

Починаючи з вершини S, послідовно «розшаровуємо» граф шляхів у дерево (рис. 19). Розставимо вздовж його ребер відстані між населеними пунктами, в кінці кожного маршруту запишемо суму цих відстаней по маршруту. З отриманих 24 маршрутів найкоротшими є SBACDS та SDCABS.

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

Задача № 2.6. Про кодування алфавіту.

Побудуйте дерево, за допомогою якого можна кодувати алфавіт з 16 літер.

Розв’язання. Розіб’ємо алфавіт на дві рівні частини. Одній групі (з номерами 1- 8) поставимо у відповідність 0, інший (з номерами 9 - 16) – 1. З кожною з груп зробимо так само. Процес продовжується доти, поки не отримаємо одного елементу групу (рис. 20). За допомогою отриманого чотириярусного дерева, пересуваючись знизу вгору (або навпаки), можна отримати код будь-якого з 16 символів.

Задача № 2.7. Про розбір арифметичного виразу.

Побудувати дерево розбору арифметичного виразу: .

Розв’язання. Арифметичні операції розташовується згідно з пріоритетом. Пріоритети операції такі: 1) для виразів без дужок найвищий пріоритет мають операції множення, ділення – дії другого ступеня, складання та віднімання мають нижчий пріоритет; 2) для виразів з дужками найвищий пріоритет мають вирази в дужках, далі пріоритети розташовуються як в 1). Арифметичні операції з однаковими пріоритетом графі розташовуються на одному ярусі (рис. 21).

Таким чином ми розглянули задачі, які можна розв’язувати за допомогою графів а саме одним з його різновидів – дерев. Ми можемо спостерігати що такий спосіб розв’язання такого типу задач не дуже громісткий і доступний нашому розумінню.

Висновки

Література

1.            Березина Л. Ю. Графы помогают решать логические задачи — Математика в школе, 1972 - №2 с. 62-68

2.            Єлісєєва О., Петров В., Графи працюють на нас - Математика в школі – 2005 - №5 с. 47-51.

3.            Оре О. «Графы и их применения» — М.: УРСС, 1963. — 175 с.

4.            Уилсон Р. « Введение в теорию графов » М., Мир, 1977

5.            Харари Ф. «Теория графов» — М.: УРСС, 2003. — 300 с.

24