Теорія графів

мал. 2.11

 

Приєднуючи S до H, ми отримаємо вже велику частину графа G, що має необхідну властивість.

Якщо ж ребро S = (А, B) є циклічним, воно належить деякому циклу С. Ми встановимо напрям на С від А до B і далі уподовж С до першої вершини D з С, що належить H (мал. 2.12)

мал. 2.12

 

Всі ці ребра ми приєднаємо до H. Нехай X - довільна вершина з  Н, а Y - будь-яка вершина із С: можна  знайти орієнтований ланцюг Р, що належить Н і що сполучає Х з A, а потім  уподовж С пройти до вершини Y з  С. Назад від Y можна пройти уздовж С до вершини D, а від неї - належним Н, орієнтованим ланцюгом Z - від D до X. Тому орієнтований граф, отриманий додаванням до Н вказаних ребер циклу С, також задовольняє необхідні умови: те, що від будь-якої з доданих вершин циклу С можна пройти до будь-якої іншої з цих вершин з дотриманням умов, пов'язаних з орієнтацією ребер; очевидно (мал. 2.12), продовжуючи цей процес, ми в кінці кінців орієнтуємо необхідним чином початковий граф G.

Встановлення на вулицях  міста одностороннього руху дозволяє сильно збільшити швидкість руху транспорту; проте воно ставить справжні головоломки перед водієм, який хоче об'їхати на машині незнайоме йому місто. Якщо на вулицях скрізь або  частково встановлений односторонній  рух, то завдання стає набагато складнішим, навіть якщо зроблено необхідне припущення про існування, принаймні одного орієнтованого ланцюга, що сполучає будь-яку пару вершин графа.

Загальна проблема така: яким способом можна рухатися по графові  уздовж вказаних напрямів, щоб зрештою  пройти по всіх його ребрах? Для цього, звичайно, треба мати хорошу пам'ять, а ще краще заздалегідь скласти  нарис графа, утвореного мережею  вулиць.

Ми відправляємося з деякої точки а0 по одній з вулиць, що виходять з неї. Проходячи перехрестя, ми позначаємо на малюнку, по якій вулиці ми сюди прийшли і на яку нову вулицю переходимо; для подальшого корисно відзначити також і інші вулиці, що виходять на це перехрестя, разом з їх напрямами. Через деякий час ми повернемося до одного з перехресть а1, на якому ми вже побували раніше (мал. 2.13).

 

мал. 2.13

 

Подивимося на план, складений  нами заздалегідь, якщо ми вже обійшли  всі вулиці міста, то наше завдання вирішене. B протилежному випадку знайдеться ще не пройдена вулиця (с, d). По припущенню існує орієнтований ланцюг, сполучаючий а1 з с; ми підемо по ньому, а потім пройдемо вулицю (с, d) (зрозуміло, найзручніше починати з не пройдених раніше вулиць, що виходять з а1) Ясно, що, діючи і далі так само, ми врешті-решт обійдемо всі вулиці міста.

Висновок: якщо органи міського управління приймуть до уваги результат дослідження цієї задачі, то затори зникнуть з вулиць будь-якого міста.

2.6 Розв'язування систем лінійних рівнянь за допомогою графів

У VII класі учні навчаються розв' язувати  системи двох лінійних рівнянь з  двома змінними графічним способом та способами підстановки і додавання. Інші, нетрадиційні способи розв' язання систем лінійних рівнянь у VII-IX класах не вивчаються. Тому розв' язування систем лінійних рівнянь, що ґрунтується на використанні графів, варто  розглянути .

За допомогою графа одну змінну можна виразити через інші, незалежно  від їх кількості. У процесі перетворення графа треба прагнути до поступового  перетворення вершин-джерел у прості каскадні.

Наприклад, розв'яжемо даним способом таку систему (рис. 2.14, назвемо її базовою):

 

 

Граф, поданий на рис.2.14а, відповідає базовій системі. Граф на рис. 2.14б, дістали змінивши сток. Вершина-джерело х перетворилась в просту каскадну вершину.

 

Рис. 2.14

Граф  на рис. 7в, дістали, змінивши послідовні й паралельні ребра графа (рис. 7б) окремими ребрами.

Розв'язування системи зводиться  до   розв' язування   рівняння   першого степеня з однією змінною, яке відповідає   графу,   зображеному   на рис. 2.14в:

 

5=12* -y;

-y = -13;

y = 2.

Щоб знайти х, треба в рівняння, що відповідає графу, поданому на рис. 2.14б, замість змінної у підставити її значення. Оскільки ребра, що виходять з вершини, на її імпульс не впливають, досить розглянути частину графа, де вершина х є стоком (рис. 2.15) і записати відповідне   рівняння: x= - + 12* ;

х = 5. Відповідь: (5;2).

На  рис. 2.16 і 2.17 подано розв'язування систем рівнянь, що не мають  розв'язку або мають нескінчену множину розв' язків.

 

 

 

Вершина, що відповідає змінній, ізольована від  стоку, оскільки вага відповідного ребра  дорівнює нулю. Згідно з прийнятими вище домовленостями таке ребро не можна побудувати.

 

 

 

Рис. 2.15

 

Рис. 2.16

Рис. 2.17

На рис. 2.16в ми маємо 9* = 8,  це неправильна числова рівність, а отже система 2 розв'язків не має. На рис. 2.17в ми   маємо   1* = .,   це   правильна числова рівність, і система 3 має нескінченну множину розв'язків.

Розв'яжемо     систему     трьох лінійних рівнянь з трьома змінними.

 

 

 

 

 

 

Рис. 2.18

 

Розв'язування системи зводиться до розв'язування рівняння першого степеня    з    однією    змінною,    яке відповідає графу, зображеному на рис. 2.18д:

 

                       6 = 5* + 1*() - z;

- z = -;

Z = 2.

Щоб знайти х, треба в рівняння, що відповідає графу, поданому на рис. 2.18г, замість змінної z підставити її значення і записати відповідне рівняння:

 

Аналогічно знаходимо у  (рис.2.18б):

Відповідь: (1;-1;2).

Так само за допомогою графів розв'язують системи лінійних рівнянь з більшою  кількістю змінних.

Висновок:Дослідження показало, що розглянутий спосіб розв'язування систем лінійних рівнянь:

1. розвиває творчу активність учнів та формує в них потребу постійно розширювати та поглиблювати свої знання;
2. розширює математичну культуру учнів і демонструє наявність нетрадиційних підходів до розв' язування математичних задач;

3) вдосконалює прийоми розумової діяльності учнів і розвиває в них дослідницький, творчий підхід до постановки і розв' язування задач з різних сфер людської діяльності.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ВИСНОВКИ

 

З розвитком комп’ютерної техніки та комп’ютеризацією виробництва  і інших галузей людської діяльності, неперервно зростає роль дискретної математики як теоретичної основи для  побудови алгоритмів і написання  комп’ютерних програм.

Теорія графів – дуже важливий розділ дискретної математики, особливістю якого є геометричний підхід до вивчення об’єктів. Діаграми графа подібно до геометричних рисунків дозволяють одержати наочне представлення  до різного роду задач.

Родоначальником теорії графів прийнято вважати Леонарда Ейлера, який у 1736 році, розв’язавши життєву задачу про Кенігсберзькі мости, встановив  властивості зв’язного графа та зробив деякі загальні висновки.

На сьогоднішній час графи  дуже зручно використовувати для  розв’язання задач різних видів. Теорія графів є дуже актуальною, її широко застосовують не тільки у самій математиці, а й в інших природничих науках – зокрема, у фізиці, хімії, географії, біології, картографії та в багатьох інших науках. Так, наприклад,  для побудови структурних формул хімічних елементів, для складання найбільш вигідних транспортних маршрутів, при моделюванні складних технологічних процесів, у програмуванні, в електротехніці – для конструювання друкованих схем, а також при вивчені послідовного і паралельного з’єднання провідників.

Граф є математичною моделлю  найрізноманітніших об’єктів, явищ і  процесів, що досліджуються і використовуються  в науці, техніці та на практиці. Графи дозволяють будувати математичну  модель зв’язків між заданими елементами.

Наприклад, у вигляді графа  можуть бути зображені електричні, транспортні, інформаційні і комп’ютерні  та інші мережі, карти автомобільних, залізничних, повітряних шляхів, лабіринти, моделі кристалів, структури молекул  хімічних речовин і т.д.

Прикладами застосування теорії графів є пошук зв’язних компонентів та пошук найкоротших, „найдешевших” та „найдорожчих”  шляхів у комунікаційних мережах. Для  побудови таких шляхів використовуються різноманітні алгоритми на графах. Отже, практична цінність теорії графів безперечна.

 

 

 

 

СПИСОК  ВИКОРИСТАНИХ ДЖЕРЕЛ

1. Берж К. Теорія графів і її застосування. - М.: МУЛ, 1962.
2. Зиков А. А. Теорія кінцевих графів. - Новосибірськ: Наука, 1969.
3. Касаткін В. Н. Незвичайні задачі математики. - К.: Радянська школа, 1987.
4. Олехнік С. Н., Нестеренко Ю. В., Потапов М. К. Стародавні цікаві задачі. - М.: Наука, 1988.
5. Оре О. Графи і їх застосування. - М.: Світ, 1965.
6. Реньє А. Трилогія про математика. - М.: Світ , 1980.
7. У світі математики: Зб. Наук.-попул. статей / Редкол.: М.Й. Ядренко (відп. ред.) та ін. – К.: Рад. школа, 1980.

8. Сарана О.А. Математичні олімпіади: просте і складне поруч: Навч.посібн.: К.: Видавництво А.С.К., 2004.

9. Барболін М.П. Головоломки і графи // Квант. - 1975. - №2. -С.59-61

10.Березіна Л.Ю. Графи і їх застосування: Посібник для вчителя. - М.: Просвіта, 1979. - 144с.

11.Слєпкань З.І. Методика навчання математики.   -  К.:   Зодіак-ЕКО, 2000. -512

12. Бардачов Ю.М., Соколова Н.А., Ходаков В.Э. Дискретна математика. – К.: Вища школа, 2002.

13. Яблонский С.В. Введення в дискретну математику. – М.: Наука, 1986.

14. Ядренко М.Й. Дискретна математика. – К.: КНУ, 2002.