Курсовая работа: Основи теорії графів. Властивості ойлерових та гамільтонових графів

ЗМІСТ

ВСТУП

РОЗДІЛ І ВВЕДЕННЯ В ТЕОРІЮ ГРАФІВ

1.1 Основні поняття та означення

1.2 Лема про рукостискання

1.3 Оцінки для числа ребер з компонентами зв ‘язності

1.4 Орієнтовані графи, графи з петлями, графи з паралельними дугами

РОЗДІЛ ІІ ОЙЛЕРОВІ ГРАФИ

2.1 Ойлерова ломиголовка «Кенігзберзьких мостів»

2.2 Основні поняття та означення ойлерових графів

2.3 Приклади ойлерових графів

РОЗДІЛ ІІІ ГАМІЛЬТОНОВІ ГРАФИ

3.1 Сутність гамільтонових графів

3.2Основні поняття та означення

3.3 Приклади гамільтонових графів

ВИСНОВКИ

СПИСОК ВИКОРИСТАНОЇ ЛІТЕРАТУРИ

ВСТУП

Роком виникнення теорії графів одностайно вважається рік 1736, коли Леонард Ойлер опублікував розв’язок так званої задачі про кенігсберзькі мости, а також знайшов загальний критерій існування ойлерового циклу в графі.

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

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

Із суто формальної точки зору граф можна розглядати як один з різновидів алгебраїчної системи (а саме, як модель), а отже, і всю теорію графів - як розділ сучасної алгебри. Справді, результати та методи алгебри широко використовуються в теорії графів. Однак за останні півстоліття активного інтенсивного та екстенсивного розвитку теорія графів виробила свою достатньо специфічну власну проблематику і методологію. На сьогодні теорія графів є однією зі складових математичного апарату кібернетики, важливим розділом дискретної математики.

В курсові роботі досліджені властивості ойлерових та гамільтонових ланцюгів та циклів в теорії графів, а також наведені приклади графів.

РОЗДІЛ І ВВЕДЕННЯ В ТЕОРІЮ ГРАФІВ

1.1 Основні поняття та означення

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

Сполучення цих елементів визначає поняття: неорієнтований граф, орієнтований граф та змішаний граф [6].

Рис.1.1. Основні елементи графу (вершина, ребро, дуга)

--> ЧИТАТЬ ПОЛНОСТЬЮ <--