РЕФЕРАТ

на тему:

“Задачі, які приводять

до поняття графа”

1. Поняття про графи

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

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

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

Задача 1:

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

що кожен знав тільки двох запрошених.

Розв”язання:

Кожного з цієї компанії зобразимо точкою, і пронумеруємо їх. Якщо двоє
знайомі, то з”єднаємо їх відрізком (ребром). Виявляється, що така
ситуація не тільки можлива, але й може описуватися декількома схемами.

Тобто можна сказати, що граф-це сукупність об”єктів, зв”язками між якими
служать ребра.

Приклади графів з декількома вершинами та ребрами.

На малюнку 4 показаний граф з чотирма вершинами та шістьма ребрами

На малюнку 5 зображено граф з п”ятьма вершинами та двома ребрами

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

2. Задача Ейлера – як яскравий приклад задачі,

яка приводить до поняття графа

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

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

розташування мостів.

Приблизно ось така >>>

 

 

 

 

Витончена по своїй конкретності Задача семи мостів Кенігсберга була
сформульована Ейлером у 1759 р. у такий спосіб: «як пройти по семи
мостах, не проходячи по одному двічі».

накласти вершини і зв’язки на карту центра нашого міста >>>>>>

 

 

Цей же граф для числа «7» у чистому виді без «підкладки». >>>

 

 

 У кожній мережі Ейлер підраховує зв’язки, що приходять у вершини. Якщо
число зв’язків непарне, таку вершину Ейлер називає «неправильною» або
«дивною». Вершина з парною кількістю зв’язків – «правильна» (у
першоджерелі – «мудра»). Як бачимо, усі вершини в нашій мережі
з’єднують 3 чи 5 зв’язків. Отже усі вони — неправильні. Виходить, так
званої безупинної «доріжки Ейлера», яка проходить через кожну вершину
тільки один раз для цього числа не існує.

А в якому випадку існує така «доріжка»?

Для рішення цієї задачі Ейлер створив і довів теорему: якщо мережа має
не більш двох «дивних» вершин, є принаймні один подібний шлях.

3. Основні теореми теорії графів

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

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

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

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

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

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

Визначення 5. Ступенем вершини називається число ребер, яким належить
вершина.

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

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

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

Визначення 9. Багатокутник плоского графа, що не містить усередині себе
ніяких чи вершин ребер графа, називають його гранню.

Визначення 10. Шляхом від A до X називається послідовність ребер, що
веде від A до X, така, що кожні два сусідніх ребра мають загальну
вершину, і ніяке ребро не зустрічається більш одного разу.

Визначення 11. Циклом називається шлях, у якому збігаються початкова і
кінцева точка.

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

Визначення 13. Довжиною шляху, прокладеного на циклі, називається число
ребер цього шляху.

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

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

Визначення 16. Деревом називається зв’язний граф, що не містить циклів.

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

Визначення 17. Незв’язний граф, що складається винятково з дерев,
називається лісом.

Визначення 13. Дерево, усі n вершин якого мають номера від 1 до n,
називають деревом з перенумерованими вершинами.

Отже, ми розглянули основні визначення теорії графів, без яких було б
неможливе доказ теорем, а, отже і рішення задач.

Використана література:

Основи вищої математики. – К., 2002.

Математична енциклопедія. – М., 1989.

Похожие записи