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

 

Міністерство  освіти і науки України

Рівненська  мала академія наук учнівської молоді

Відділення математики

Секція прикладної математики

 

 

 

 

 

 

 

 

 

 

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

 

 

 

 

 

 

Науково-дослідницька робота                 

 

 

 

 

 

 

 

 

 

 

 

Рівне 2009

Зміст

Вступ……………………………………………………………………………………….......3

1. Історія виникнення графів……………………………………………………………... 4
2. Основні означення теорії графів……………………………………………………...... 7
3. Основні теореми теорії графів…………………………………………………………14
4. Задачі на застосування теорії графів……………………………………………….. ...18
5. Застосування теорії графів у різних галузях науки і техніки…………………………..29

Висновки………………………………………………………………………......................31

Список використаних джерел

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ВСТУП

Спробуйте намалювати „заклеєний конверт" одним розчерком пера, тобто не відриваючи ручки від паперу й не проводячи двічі один і той самий відрізок. Такого роду запитання з давніх-давен цікавили математиків.

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

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

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

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

 

 

 

 

 

 

 

 

 

 

 

 

1. ІСТОРІЯ   ВИНИКНЕННЯ ТЕОРІЇ ГРАФІВ.

Родоначальником теорії графів прийнято вважати математика Леонарда

Ейлера  (1707-1783рр.).   Історію   виникнення   цієї  теорії  можна   простежити   з листування великого вченого. Ось переклад латинського тексту, взятий з листа Ейлера до італійського математика й інженера Маріоні, відправленого з Петербурга 13 березня 1736 року [5,с. 41-42]:

"Якось мені була запропонована задача про острів, який розташований в місті Кенігсберзі та оточений рікою, через яку перекинуто сім мостів. Запитується, чи може хто-небудь безупинно обійти їх, проходячи тільки один раз через кожен міст. І відразу мені було повідомлено, що ніхто ще дотепер не міг це зробити, але ніхто і не довів, що це неможливо. Це питання хоч і банальне, проте здалось менш гідним уваги тим, що для його рішення недостатні ні геометрія, ні алгебра, ні комбінаторне мистецтво... Після довгих міркувань я легко знайшов правило, засноване на цілком переконливому доказі, за допомогою якого можна у всіх задачах такого типу негайно ж визначити, чи може бути зроблений такий обхід через яке завгодно число і як завгодно розташованих мостів. Кенігсберзькі ж мости розташовані так, що їх можна подати на наступному малюнку (рис. 1.1), на якому А позначає острів, а В, С і D — частини континенту, відділені один від одного рукавами ріки. Сім мостів позначені буквами a, b,c_t d, e,f,g"

Рис. 1.1. Розташування Кенігсберзьких мостів

З приводу  виявленого ним способу вирішувати задачі подібного роду

Ейлер писав [5, с. 102-104]:

                  "Це рішення за своїм характером , очевидно, мало стосується математики, і мені незрозуміло, чому випливає, що швидше від математика слід очікувати цього рішення, ніж від будь-якої іншої людини, тому що це рішення підкріплюється одним тільки міркуванням, і немає необхідності залучати для знаходження цього рішення які-небудь закони, властиві математиці. Отже, я не знаю, яким чином виходить, що питання, що мають зовсім мале відношення до математики, скоріше вирішується математиками, чим, іншими."

Ейлер позначив на карті міста по одній точці на кожному березі річки і на кожному острові. Потім  він з'єднав ці точки відповідно до розташування мостів. Вийшов такий  малюнок :

Рис. 1.2. Зображення Кенігсберзьких мостів Ейлером

Тепер задача обходу мостів звелася до задачі зображення одержаної  картинки одним розчерком. Картинки подібні до цієї, тобто такі, що складаються із кількох точок (їх стали називати вершинами) і кількох дуг, що з'єднують деякі з цих точок (їх почали називати ребрами), дістали назву графів. З дворянським титулом їх поєднує спільне походження від латинського слова "графіо" - пишу. Вперше термін „граф" ввів угорський математик Денеш Кенігу 1936 році. Та повернемось до Кенігсберзької задачі.

Так чи можна обійти Кенігсберзькі  мости, проходячи тільки один раз  через кожний з цих мостів? Щоб знайти відповідь, продовжимо лист Ейлера до Маріоні:

 

 

   "Питання полягає в тому, щоб визначити, можна чи не можна обійти всі ці сім мостів, проходячи через кожен тільки один раз. Моє правило приводить до наступного рішення цього питання. Насамперед, потрібно дивитися, скільки є ділянок, розділених водою, — таких, у яких немає іншого переходу з одної на іншу, крім як через міст. У даному прикладі таких ділянок чотири — А, В, С, D. Далі потрібно розрізняти, чи є число мостів, що ведуть до цих окремих ділянок, парним чи непарним. Так, у нашому випадку до ділянки А ведуть п'ять мостів, а до інших - по три мости , тобто число мостів, що ведуть до окремих ділянок, непарне, а цього вже досить для рішення задачі. Коли це визначено, застосовуємо наступне правило: якби число мостів, що ведуть до кожної окремої ділянки, було парним, тоді обхід, про який йде мова, був би можливий, і в той же час можна було б почати цей обхід з будь-якої ділянки. Якщо ж з цих чисел два були б непарні, тому що тільки одне бути непарним не може, то і тоді міг би здійснитися перехід, як це запропоновано, але тільки початок обходу неодмінно повинний бути взятий від одної з тих двох ділянок, до яких веде непарне число мостів. Якби, нарешті, було більше двох ділянок, до яких веде непарне число мостів, то тоді такий рух узагалі неможливий... Якщо можна було б привести тут інші, більш серйозні задачі, цей метод міг би принести ще велику користь і нам не варто було б ним зневажати.

Обґрунтування вищенаведеного правила  теж можна знайти в одному з  листів Л. Ейлера.

Математик писав, що перехід можливий, якщо розгалуження ріки має не більш  двох областей, у які веде непарне  число мостів. Для того, щоб простіше уявити собі це, будемо стирати на малюнку  вже пройдені мости. Легко перевірити, що якщо ми почнемо рухатися відповідно до правил Ейлера, перетнемо один міст і зітремо його, то на малюнку  буде зображена ділянка, де знову  є не більш двох областей, у які  веде непарне число мостів, а при  наявності областей з непарним числом мостів ми будемо розташовуватися в  одній з них. Продовжуючи рухатися так далі, пройдемо через усі мости  по одному разу.

Задача про Кенігсберзькі мости  і подібні їй задачі разом із сукупністю методів їхнього дослідження  складають дуже важливий у практичному  відношенні розділ математики, названий теорією графів. Перша робота про  графи належала Л. Ейлеру і з'явилася  в 1736 році. Надалі над графами працювали  Кеніг (1774-1833), Гамільтон (1805-1865), із сучасних математиків - К. Берж, О. Оре, А.Зиков.

 

 

2. ОСНОВНІ ПОНЯТТЯ ТЕОРІЇ ГРАФІВ

Теорія графів - дисципліна математики,   тому її виклад містить у собі і необхідні строгі визначення. А саме:

Означення 2.1. Графом називається сукупність скінченого числа точок, (вершин графа), і відрізків, що попарно з'єднують ці точки (ребра чи дуги графа).

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

На рис.2.1,а показано граф з чотирма вершинами та шістьма ребрами, на рис.2.1,б - зображено граф з п'ятьма вершинами та двома ребрами.

 

 

а) 

б)

Рис. 2.1. Приклади графів

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

Означення 2.2. Вершини графа, що не належать жодному ребру, називаються ізольованими.

Означення   2.3. Граф,   що  складається  тільки   з   ізольованих  вершин, називається нуль-графом.

Позначення: О' — граф з вершинами, що не має ребер.

Означення 2.4. Граф, у якому кожна пара вершин з'єднана ребром, називається повним.

Позначення: U' - граф, що складається з п вершин і ребер, що з'єднують всі пари цих вершин. Такий граф можна представиш як п-кутник, у якому проведені всі діагоналі. Такий граф зображений на рис.2.1,а.

Але графи можуть бути і неповними, наприклад, граф представлений  на рис.2.1,6. Такі графи можна перетворити у повні з тими ж вершинами, прибавивши ребра, яких не вистачає. Позначимо цей граф Г. Провівши потрібні ребра, ми отримаємо повний граф з такою ж кількістю вершин (рис.2.2). Вершини графа Г і добавлені ребра також утворюють граф, який називається доповненням графа.

Рис. 2.2. Утворення повного графа.

Означення 2.5. Доповненням  графа Г називається  граф Г2 з тими ж вершинами, що і граф Г, і з тими і тільки тими ребрами, які необхідно додати до графа Г, щоб отримати повний граф (рис.2.3)

Рис. 23. Доповнення графа.

       Означення 2.6. Степенем вершини називається число ребер, до яких належить вершина.

Позначення: р (А) — степінь вершини А.

Наприклад, в графі, показаному на рис. 2.4:

Вершина А має степінь 3; Вершина D має степінь 1; Вершина В має степінь 2.

Рис. 2.4. Степінь вершини.

Степінь кожної вершини повного  графа на одиницю менша числа  його вершин. Вершина називається парною, якщо її степінь — число парне. Вершина називається непарною, якщо її степінь — число непарне.

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

Означення 2.7. Граф, степені всіх вершин якого однакові і дорівнюють к, називається однорідним графом, степеня k.

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

 

Рис. 2.5. Плоский граф.

На рис. 2.5,а - зображено граф, деякі ребра якого перетинаються,

на рис.2.5,6- зображено той самий граф так, щоб ребра не перетиналися.

Означення 2.9. Шляхом від А до X називається така послідовність ребер, що веде від A до Х,в якій кожні два сусідніх ребра мають спільну вершину. Вершина А-початок шляху, вершина X - кінець. Згідно з означенням, вершини шляху можуть повторюватися. Шлях з А до X називається простим, якщо він не проходить через жодну вершину більше одного разу.

Наприклад, як можна пройти з вершини  А у вершину F ?

Рис. 2.6. Шлях графа.

Можливі різні варіанти розв'язку:

1) A, D, F; 2) А, В, D, F; 3) A, D, В, A, D, F.

Можна вказати маршрут  від А до F, який включає всі вершини графа. Наприклад (А, В, D, C, A, D, F).

Означення 2.10. Довжиною шляху називається число ребер цього шляху.

Означення 2.11. Циклом називається шлях, у якому співпадають початкова і кінцева вершини.

Означення 2.12. Простим циклом називається цикл, що не проходить через одну з вершин графа більш одного разу.

На рис. 2.7. зображено простий цикл А-В-С-А.

 

 

 

 

Рис. 2.7. Простий цикл.

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

Довжиною циклу називають число ребер в циклі.

Означення 2.13. Грань графа - це частина площини, яка обмежена простим циклом і не містить всередині інших циклів.

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

Означення 2.14. Дві вершини А і В у графі називаються зв'язними (незв'язними), якщо в ньому існує (не існує) шлях, що веде з А до В.