Основні поняття теорії графів (реферат)
Витончена по своїй конкретності Задача семи мостів Кенігсберга була сформульована Ейлером у 1759 р. у такий спосіб: «як пройти по семи мостах, не проходячи по одному двічі». Визначення 7. Доповненням даного графа називається граф, що складається з усіх ребер і їхніх кінців, які необхідно додати до вихідного графа, щоб одержати повний граф. Це визначення можна сформулювати інакше: графом… Читати ще >
Основні поняття теорії графів (реферат) (реферат, курсова, диплом, контрольна)
РЕФЕРАТ
на тему:
" Основні поняття теорії графів"
Засновником теорії графів прийнято вважати математика Леонарда Ейлера (1707−1782). Теорія графів — дисципліна математична, створена зусиллями математиків, тому її виклад включає в себе і необхідні чіткі визначення.
Поняття про графи
Для вирішення багатьох задач, може бути застосоване таке поняття, як граф.
Граф — це множина точок (вершин), які з'єднані між собою лініями, що називаються дугами або ребрами.
Приведемо приклад задачі, яка може бути розв’язана, за допомогою графів.
Задача 1:
На вечірку запрошено шестеро людей, чи може бути така ситуація,.
що кожен знав тільки двох запрошених.
Розв’язання:
Кожного з цієї компанії зобразимо точкою, і пронумеруємо їх. Якщо двоє знайомі, то з'єднаємо їх відрізком (ребром). Виявляється, що така ситуація не тільки можлива, але й може описуватися декількома схемами.
.Тобто можна сказати, що граф-це сукупність об'єктів, зв’язками між якими служать ребра.
Приклади графів з декількома вершинами та ребрами.
На малюнку 4 показаний граф з чотирма вершинами та шістьма ребрами.
На малюнку 5 зображено граф з п’ятьма вершинами та двома ребрами.
мал.4 мал.5.
Прикладами графів можуть слугувати схеми метрополітенів, схеми шосейних чи залізничних доріг, карти, які показують зв’язки між окремими об'єктами.
Задача Ейлера — як яскравий приклад задачі,
яка приводить до поняття графів
Для рішення серйозних математичних задач математик Ейлер використовував наочні головоломки. Одна з них поклала початок зовсім новій області досліджень, що виросла згодом у самостійний розділ математики — теорію графів і топологію. Особливість цієї теорії - у геометричному підході до вивчення об'єктів.
Буваючи в Кенігсберзі, прогулюючи по його набережних, Ейлер звернув увагу на оригінальне розташування семи мостів міста. Причиною цьому був вигадливий течії рукавів Прегеля, з'єднаних протокою, що охоплюють з півночі і півдня острів Кнайпхоф, а потім зливаються разом.
У підручниках зображується схема розташування мостів.
Приблизно ось така >>>
Приблизно ось така >>>Витончена по своїй конкретності Задача семи мостів Кенігсберга була сформульована Ейлером у 1759 р. у такий спосіб: «як пройти по семи мостах, не проходячи по одному двічі» .
Для рішення цієї задачі Ейлер вводить поняття «мережі» (щоназивається в наш час «графом») як безлічі непересічних ребер чи зв’язків, що з'єднують пари вершин. Ось так виглядає цей граф, якщо.
накласти вершини і зв’язки на карту центра нашого міста >>>>>>
накласти вершини і зв’язки на карту центра нашого міста >>>>>>Цей же граф для числа «7» у чистому виді без «підкладки». >>>
Цей же граф для числа «7» у чистому виді без «підкладки». >>>
Цей же граф для числа «7» у чистому виді без «підкладки». >>>У кожній мережі Ейлер підраховує зв’язки, що приходять у вершини. Якщо число зв’язків непарне, таку вершину Ейлер називає «неправильною» або «дивною». Вершина з парною кількістю зв’язків — «правильна» (у першоджерелі - «мудра»). Як бачимо, усі вершини в нашій мережі з'єднують 3 чи 5 зв’язків. Отже усі вони — неправильні. Виходить, так званої безупинної «доріжки Ейлера», яка проходить через кожну вершину тільки один раз для цього числа не існує.
А в якому випадку існує така «доріжка»?
Для рішення цієї задачі Ейлер створив і довів теорему: якщо мережа має не більш двох «дивних» вершин, є принаймні один подібний шлях.
Основні теореми теорії графів.
Теорія графів, як було сказано вище, — дисципліна математична, створена зусиллями математиків, тому її виклад містить у собі і необхідні строгі визначення. Отже, приступимо до організованого введення основних понять цієї теорії.
Визначення 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, називають деревом з перенумерованими вершинами.
Отже, ми розглянули основні визначення теорії графів, без яких було б неможливе доказ теорем, а, отже і рішення задач.
Використана література:
1.Берж К. «Теория графов и ее применение», М., ИЛ, 1962;
2.Зыков А. А. «Теория конечных графов», Новосибирск, «Наука», 1969;
3.Основи вищої математики. — К., 2002.
4.Оре О. «Графы и их применения», М. «Мир», 1965;