Поняття та характеристика терміну "Ейлерові графи", основні відомості і теореми, пов’язані з цим поняттям. Задача про кенігсберзькі мости, оцінка числа ейлеровими графами. Алгоритм побудови Ейлерового кола. Розповсюдження та популярність ейлерових графів.
Аннотация к работе
Перша робота з теорії графів, що належить відомому швейцарському математику Л. Спочатку теорія графів здавалася досить незначним розділом математики, так як вона мала справу в основному з математичними розвагами й головоломками. В даний час ця теорія знаходить численне застосування в різноманітних практичних питаннях: при встановленні різного роду відповідностей, при вирішенні транспортних задач, задач про рух інформації у мережі нафтопроводів, в програмуванні та теорії ігор, теорії передачі повідомлень.Граф G - пара (V, X), де V кінцеве непорожнє безліч, що містить p вершин, а безліч Х містить q невпорядкованих пар різних вершин з V. Кожну пару X = {u, v} вершин у Х називають ребром графа G і кажуть, що Х зєднує u і v. Якщо два різних ребра X і Y інцидентних однієї і тієї ж вершині, то вони називаються суміжними. Граф з р вершинами і q ребрами називається (p; q) - графом. Типи графів: · Мультиграф, в ньому не допускаються петлі, але пари вершин можуть зєднуватися більш ніж одним ребром, ці ребра називаються кратними.Граф G / (U /, V /) називається подграфом графа G (U, V), якщо U / IU і V / IV. Маршрутом у графі G називається чергується послідовність вершин і ребер v 0, x 1, v 1, ... v n-1, x n, v n; ця послідовність починається і закінчується вершиною, і кожне ребро послідовності інцидентне двом вершин, одна з яких безпосередньо передує йому, а інша безпосередньо слідує за ним. Маршрут називається ланцюгом, якщо всі його ребра різні, і простий ланцюгом, якщо всі вершини (а отже, і ребра) різні.Вирушаючи від цього окремого випадку Ейлер узагальнив постановку задачі і знайшов критерій існування обходу у даного графа, а саме граф повинен бути звязковим і кожна його вершина має бути інцедентна кратному числа ребер. Задачу про обхід мостів можна узагальнити і отримати таку задачу теорії графів: чи можна знайти в даному графі G цикл, у якому всі вершини і всі ребра? Граф з більш ніж однією вершиною має Ейлером цикл тоді і тільки тоді, коли він звязний і кожна його вершина має парну ступінь. Припустимо, що кожен звязний граф, що має менш k вершин, і всі вершини якого мають парному ступенем, містить Ейлером цикл. Нехай e - ребро графа G /, нехай G e - компонента графа G /, що містить тобто Оскільки G / має менше, ніж k, вершин, і в кожної вершини графа G / парна ступінь, граф G / має Ейлером цикл.У даній роботі були розглянуті основні поняття теорії графів, їх види. Велику увагу приділили питанню існування в них ейлеревих ланцюгів і циклів, розглянули ряд теорем і властивостей.
План
Зміст
Введення
Глава 1. Теоретична частина
1.1 Основні поняття теорії графів
1.2 Маршрути і звязність
1.3 Задача про кенігсберзькими мостах
1.4 Ейлерови графи
1.5 Оцінка числа ейлеровим графів
1.6 Алгоритм побудови Ейлера кола в цьому ейлеровим графі
Висновок
Література
Вывод
У даній роботі були розглянуті основні поняття теорії графів, їх види. Велику увагу приділили питанню існування в них ейлеревих ланцюгів і циклів, розглянули ряд теорем і властивостей. Описали алгоритм знаходження ейлеревого циклу в довільному графі, а в практичній частині показали його застосування на конкретних прикладах.
Відомо, що Ейлерові графи отримали широке розповсюдження і популярність завдяки тому, що багато головоломки і завдання можна вирішити з використанням знань теорії графів. Приватні приклади таких головоломок і сюжетних завдань були приведені в практичній частині. Задачі на відшукання шляхів через лабіринти, близькі до завдань на Ейлерові графи, знаходять застосування в сучасній психології і при конструюванні обчислювальних машин. Також з практичної точки зору, зараз графи застосовують у багатьох інших областях науки таких як: програмування, фізика, хімія, біологія, економіка і т.д.
Список литературы
1. Андерсон, Джеймс А. Дискретна математика і комбінаторика: пров. з англ. - М.: Видавничий дім «Вільямс», 2003. - 960с.
2. Березіна Л. Ю. Графи і їхнє застосування. - М.: Просвещение, 1979.
3. Новіков С.А. Дискретна математика для програмістів - СПБ.: Питер, 2001. - 304с.
4. Оре о. Графи і їхнє застосування. - М.: Світ, 1973.
5. Уілсон Р. Введення в теорію графів. - М.: Світ, 1977.