Автор: Пользователь скрыл имя, 21 Февраля 2013 в 14:57, курсовая работа
Метою дослідження було ознайомитися з історією виникнення теорії графів, дати основні означення та теореми графів та показати їх роль для сучасної науки і техніки.
Спробуйте намалювати „заклеєний конверт” одним розчерком пера, тобто не відриваючи ручки від паперу й не проводячи двічі один і той самий відрізок. Такого роду запитання з давніх-давен цікавили математиків.
Зрозуміло, часто трапляється, що потреби практики підштовхують розвиток математики. Яскраві приклади цього – теорії, створені М. Келдишем для авіаконструкторів. Досить часто поняття математики виникали з необхідності – так було з векторами, логарифмами, тригонометрією... Проте, нерідко математика є відірваною від реального життя, а тоді раптом виявляється, що в хащі неправдоподібності її все таки не занесло. Хрестоматійним прикладом є вчення про графи.
Декілька століть тому математиків, які досліджували дану проблему називали диваками і мрійниками. А сьогодні сучасні досягнення теорії графів використовуються у різних галузях знань, що підкреслює наукову та практичну значимість цієї проблеми.
В наш час теорія графів є дуже актуальною. Вона використовується у багатьох сферах людського життя для опису взаємозв’яків між об’єктами, процесами чи подіями. Граф – це досить чітка модель для вивчення окремих явищ навколишньої дійсності. Тому темою моєї дипломної роботи є «Графи, деякі їх застосування та методика вивчення у шкільному курсі математики», адже теорія графів має не тільки наукову, а й практичну цінність. Останнім часом зв’язані з графами методи досліджень використовуються не тільки в математиці, але і у фізиці, хімії, біології, географії та інших науках.
Отже, об’єктом дослідження в даній дипломній роботі виступає теорія графів, основні теореми теорії графів та їх застосування при розв’язуванні задач.
Метою мого дослідження було ознайомитися з історією виникнення теорії графів, дати основні означення та теореми графів та показати їх роль для сучасної науки і техніки.
Предметом дослідження є застосування теорії графів при розв’язанні завдань різних видів, вивчення елементів теорії графів у загальноосвітній школі, а саме на спецкурсах з математики у 10-11-х класах.
Дослідженням теорії графів займалися багато науковців сучасності, серед них: кандидат фізико-математичних наук, професор Р.М. Трохимчук, доктор фізико-математичних наук, професор Сущанський В.І., кандидат фізико-математичних наук, доцент Шевченко В.П., кандидат фізико-математичних наук Зиков А. А., кандидат фізико-математичних наук Берж К., кандидат фізико-математичних наук Оре О..
Граф - фігура, що складається з точок (вершин) і відрізків, що сполучають деякі з цих вершин. Сполучаючі відрізки можуть бути прямолінійними або криволінійними; вони називаються ребрами графа.
Основні елементи геометричних фігур, які застосовуються у теорії графів наведені на рис.1. та складаються з вершин графу, ребер графу та дуг графу.
Сполучення цих елементів визначає поняття: неорієнтований граф, орієнтований граф та змішаний граф.
Рис.1.1. Основні елементи графу (вершина, ребро, дуга)
Неорієнтований граф (неограф) — це граф (рис.1.2), для кожного ребра якого несуттєвий порядок двох його кінцевих вершин.
Рис.1.2. Неорієнтований граф (вершини та ребра)
Орієнтований граф (орграф) — це граф, для кожного ребра якого істотний порядок двох його кінцевих вершин. Орграф представлений на рис.1.3, ребра орграфа іноді називають дугами.
Рис. 1.3. Орієнтований граф
Рис. 1.4. Змішаний граф
Змішаний граф (рис.1.4) – це граф, що містить як орієнтовані, так і неорієнтовані ребра.
Кожної з перерахованих видів графа може містити одне або кілька ребер, у яких обидва кінці сходяться в одній вершині, такі ребра називаються петлями (рис.1.5).
Рис. 1.5. Змішаний граф з петлями
Рис. 1.6. Загальний випадок графа
У загальному випадку множина ребер може складатися із трьох непересічних підмножин: підмножини ланок, підмножини дуг і підмножини петель (рис.1.6).
Рис.1.7. Сутність геометричної конфігурації графа, в якому всі вершини можна обійти за маршрутом без перетинання ребер графу.
Наочно граф можна уявляти як геометричну конфігурацію ( див. рис.1.7), яка складається з точок (вершин графу 1,2,3,4,5,6) і ребер (ліній або відрізків №1(1-3), №2(3-4), №3(4-5), №4(3-5), №5(2-3), №6(2-5), №7(5-6), №8(6-2), №9(2-1), які сполучають деякі точки (вершини) за вибраним алгоритмом обходу вершин графу).
Дамо формальне математичне означення графа.
Нехай – деяка скінченна множина (множина вершин), – множина всіх невпорядкованих пар елементів (ребер або дуг графу) з множини вершин, .
Означення 1.1
Граф – пара множин. Множина – це множина вершин, множина, – це множина ребер. Якщо , то ми говоримо, що ребро сполучає вершину з вершиною ; інша термінологія – ребро і вершини та – інцидентні.
Означення 1.2.
Граф називається повним, якщо , тобто граф складається з максимально можливої кількості ребер, які попарно з’єднують точки його вершин (див.рис.1.8). Якщо множина містить вершин, то, очевидно , число ребер повного графа дорівнює .
Рис.1.8. Приклади повних графів
Означення 1.3.
Граф називається порожнім, якщо , тобто граф не має ребер (див.рис.1.9).
Рис.1.9. Приклад побудови 3-х вершинного графу з різною кількістю ребер (заповнення графу від «порожнього» до «повного»)
Природно виникає питання: скільки є різних графів з множиною вершин , якщо . Для цього доведемо наступну теорему.
Теорема 1.1.
Число усіх різних графів з вершинами дорівнює:
Доведення. Справді, граф повністю визначено, якщо вказано множину , яка є підмножиною . Множина містить елементів, тому число усіх її підмножин дорівнює .
Означення 1.4.
Вершини та графа інцидентні, якщо .
Означення 1.5.
Степенем вершини графа називається число вершин , які інцидентні вершині ( число відрізків, які виходять з вершини ) – див.рис.1.10.
Рис.1.10. Визначення степенів вершин графу по кількості ребер, що виходять із вершин
Означення 1.6.
Якщо , то вершина називається кінцевою вершиною графа . Якщо , то вершини називається ізольованою(див рис. 1.11)
Рис.1.11. Визначення кінцевих та ізольованих вершин графа
Теорія графів багаторазово перевидається різними авторами при вирішенні різних прикладних завдань.
1. Задача про Кенігсберські мости. Обійти всі чотири частини суші, пройшовши по кожному мосту один раз, і повернутися у вихідну точку (рис. 1.12). Це завдання було вирішене Ейлером в 1736році.
Рис. 1.12. Ілюстрація до задачі про Кенігсберські мости
2. Задача про три будинки і три криниці. Є три будинки і три криниці. Провести від кожного будинку до кожного колодязя стежку так, щоб стежки не перетиналися (рис. 1.13). Це завдання було вирішене Куратовським в 1930 році.
Рис.1.13. Ілюстрація до задачі про три будинки і три криниці
3. Завдання
про чотири кольори. Будь-яку
карту на площині розфарбувати чотирма
кольорами так, щоб ніякі
дві сусідні області не були зафарбовані
одним кольором (рис. 1.14).
.
Рис. 1.14. Ілюстрація до задачі про чотири кольори
Введемо наступні операції над графами:
1. Граф G(X,W) є сумою (об’єднанням) графів G (X1 , W1), ... , G(Xk , Wk), якщо , X= , W=.
Ця сума називається прямою, якщо X i X j=, ij.
2. Граф G(X,W) називається зв’язним, якщо будь-які дві вершини xi та xj (xi X, xj X) сполучені ланцюгом з початком в xi і кінцем в xj. З симетрії випливає, що в цьому випадку і вершина xj сполучена з вершиною xi.
3. Перетином і різницею графів G (X1, W1) і G (X2 , W2) з однаковими множинами вершин називаються графи G’( X, W1W2) і G”(X , W1 \W2) відповідно; позначаються G’ =G1 G2 і G1 \ G2 = G”.
4. Доповненням графа G(X,W) називається граф = (X , M2 \ W ); отже, граф має ту саму множину вершин X, що й граф G, а будь-які дві вершини графа , суміжні тоді і тільки тоді, коли вони несуміжні в G.
5. Граф G(X,W) називається двочастковим, якщо існує таке розбиття множини його вершин X на дві підмножини (частки) X1 і X2, що кінці будь-якого ребра графа G належать різним часткам.
6. Двочастковий граф називається повним двочастковим графом, якщо будь-які дві його вершини, що належать різним часткам, є суміжними. Повний двочастковий граф, частки якого X1 і X2 складаються з n і m вершин відповідно, позначається Kn, m.
7. Операція вилучення вершини x із графа G(X,W) полягає у вилученні з множини X елемента x , а з множини W – усіх ребер, інцидентних x.
8. Операція вилучення ребра w з графа G(X,W) полягає у вилученні елемента w з множини W . При цьому всі вершини зберігаються.
Нехай є кілька різних вакантних посад і група людей, які бажають їх зайняти, причому кожен із претендентів достатньо кваліфікований для кількох, але не для всіх наявних посад.
Чи можна кожному з цих людей надати одну з тих посад, які йому підходять?
Ми можемо знову проілюструвати цю задачу за допомогою деякого графа, що в даному випадку виглядає особливо. Як уже сказано, є певна група людей, яку ми позначимо як М і деяка множина посад Р. Будуємо граф, проводячи ребра(М,Р), що з’єднує кожну людину М з тими посадами Р, які він може зайняти. На цьому графі не буде ребер, що з’єднують між собою дві вершини М чи Р, тому такий граф має вигляд: (мал. 2.1)
мал. 2.1
Завжди знайти підходяще місце для кожного претендента ми не можемо: для цього необхідно, щоб посад було не менше ніж претендентів. Але цього недостатньо.
Нехай, наприклад, група претендентів складається з двох столярів і людини, яка може працювати і столяром і сантехніком, і для них є чотири посади: одне місце столяра і три місця сантехніка. Тоді, очевидно, один столяр залишиться без роботи, хоча в даному випадку місць більше ніж претендентів, і хоча серед претендентів є люди що можуть працювати на двох посадах.
Припустимо, що загальна кількість претендентів - N. Для розв’язання задачі повинна виконуватись наступна умова:
Яку б групу із k чоловік, k=1,2,...,N, ми не взяли, повинно бути принаймні k посад, кожну з яких може займати хоча б один із наших претендентів.
Наприклад, якщо одна з осіб є столяром, а друга - одночасно і столяром, і сантехніком, і якщо є два місця сантехніка, то наша умова виконується при k=2, але не виконується при k=1; тому вказані люди не можуть одночасно влаштуватися на роботу.
Виділену умову ми коротко назвемо умовою різноманітності.
Висновок: вищенаведена задача може використовуватись працівниками служби зайнятості для правильного розміщення працівників на посади.
Ця задача про встановлення на графі деякої відповідності між його вершинами може мати і багато інших формулювань.
Припустимо, наприклад, що у нас є група із k хлопців і k дівчат. Дехто з них уже знайомі між собою, і виникає питання: в якому випадку можна розбити цих молодих людей на пари для танців так, щоб всі хлопці танцювали зі знайомими дівчатами?
Можна також змінити цю задачу: в маленькому селі є однакова кількість дорослих хлопців і дівчат; звичаєм не допускається, щоб хлопець одружувався на близькій родичці - сестрі, названій сестрі або двоюрідній сестрі. За якої умови для хлопця знайдеться наречена з цього села? Знову ми можемо розв’язати цю задачу за допомогою дводольного графа - в цьому випадку його вершини будуть з’єднані ребрами лише тоді, коли відповідні люди не є родичами.
А ось іще один варіант цієї задачі. В деякій школі є кілька гуртків: C1,C2,…,CN. Кожен із цих гуртків повинен мати старосту.
Для того щоб виключити перевантаження учнів, була поставлена умова, щоб жоден учень не був старостою більш, ніж одного гуртка. За якої умови це можливо?
Зрозуміло, що це можливо не завжди; якщо кількість гуртків в порівняно невеликій школі дужу велика, то це неможливо.
Щоб розв’язати цю задачу, ми знову звернемось до дводольного графа.
В цьому випадку одна множина вершин графа складатиметься із N гуртків, а інша множина вершин P - це множина всіх учнів школи. Ми проводимо ребро від гуртка С1 до учня р в тому випадку, якщо р є членом С1. При цьому умова різноманітності перетворюється в наступне: кожна група із k гуртків (при k = 1, 2,..., N) повинна включати щонайменше k різних учнів. Згідно вище вказаному - це та умова за якої гуртки можуть мати різних старост.
Якщо кількість гуртків занадто велика, не завжди легко довести справедливість умови різноманітності. Тому поставимо питання так: Чи можна вказати яке-небудь просте правило формування гуртків, що гарантує можливість вибору для них різних старост?