ПОМОРСЬКИЙ ДЕРЖАВНИЙ УНІВЕРСИТЕТ
ім. М.В. Ломоносова
В
Курсова РОБОТА
Ейлерова ГРАФИ
В
Виконала студентка 4 курсу
42 групи математичного
факультету Катишева Н.Г.
Науковий керівник:
Токаревська С.А.
Архангельськ
2004
Зміст
В 3
Глава 1. Теоретична частина ................................................ ............. 4
Основні поняття теорії графів ................................................. .... 4
Маршрути і зв'язність ............................................ ........................... 6
Задача про кенігсберзькими мостах ................................................. .... 7
Ейлерови графи ............................................. ................................... 9
Оцінка числа ейлерових графів ........................................... ........... 13
Алгоритм побудови ейлеровой кола в цьому ейлерова графі. 14
Глава 2. Практична частина ................................................ ............. 15
24 25
Введення
Перша робота з теорії графів, що належить відомому швейцарському математику Л. Ейлера, з'явилася в 1736г. Спочатку теорія графів здавалася досить незначним розділом математики, так як вона мала справу в основному з математичними розвагами та головоломками. Однак подальший розвиток математики і особливо її додатків дало сильний поштовх розвитку теорії графів. Вже в XIX столітті графи використовувалися при побудові схем. p> В даний час ця теорія знаходить численне застосування в різноманітних практичних питаннях: при встановленні різного роду відповідностей, при вирішенні транспортних задач, задач про потоках в мережі нафтопроводів, в програмуванні та теорії ігор, теорії передачі повідомлень. Теорія графів тепер застосовується і в таких областях, як економіка, психологія і біологія.
У цій роботі ми докладніше розглянемо Ейлерови графи, основні відомості і теореми, пов'язані з цим поняттям. А також завдання, які вирішуються за допомогою ейлерових графів. <В
Глава 1. Теоретична частина.
В
Основні поняття теорії графів
Граф G - пара (V, X), де V кінцеве непорожнє безліч, що містить p вершин, а безліч Х містить q невпорядкованих пар різних вершин з V.
Кожну пару X = { u , v } вершин у Х називають ребром графа G і кажуть, що Х з'єднує u і v . Ми писатимемо X = uv і говорити, що u і v - суміжні вершини. Вершина u і ребро Х інцидентні, так само як v і Х. Якщо два різних ребра X і Y інцидентні однієї і тієї ж вершині, то вони називаються суміжними. Граф з р вершина...
