Графи та їх застосування

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

ВСТУП 4
РОЗДІЛ 1. ЗАГАЛЬНІ ВІДОМОСТІ ПРО ТЕОРІЮ ГРАФІВ 8
1.1. Що таке граф? 8
1.1.1. Задача про кенігсберзькі мости 9
1.1.2. Основні поняття теорії графів 12
1.2. Основні способи задання графів 19
1.2.1. Задання графа за допомогою матриці інцидентності та списку ребер 19
1.2.2. Задання графа за допомогою матриці суміжності 22
1.3. Ізоморфізм графів 24
1.4. Планарність графів 28
1.4.1. Застосування теореми Ейлера до деяких завдань 31
1.4.2. Критерії планарності 34
1.5. Одна задача про плоскі графи 38
1.6. Ейлерові графи 41
1.7. Маршрути та зв′язність у графах 46
1.8. Дерева та ліси 53
РОЗДІЛ 2. ОРІЄНТОВАНІ ГРАФИ ТА РОЗФАРБУВАННЯ ГРАФІВ 57
2.1. Орієнтовані графи 57
2.1.1. Модель орграфа 57
2.1.2. Маршрути в орграфах 60
2.1.3. Турніри 63
2.2. Розфарбування графів 65
2.2.1. Хроматичне число графа 65
2.2.2. Гіпотеза чотирьох фарб та теорема про п’ять фарб для 67
планарних графів 67
РОЗДІЛ 3. ЗАСТОСУВАННЯ ТЕОРІЇ ГРАФІВ В ОКРЕМИХ ГАЛУЗЯХ НАУКИ 71
3.1. Фізика 71
3.2. Хімія 77
3. 3. Біологія і психологія 80
3.4. Інформатика 81
3.4.1. Програмування 82
3.4.2. Графи як об’єкти обробки інформації 83
3.5. Математика 88
РОЗДІЛ 4. ГРАФИ В ШКІЛЬНОМУ КУРСІ МАТЕМАТИКИ 97
4.1. Аналіз навчальних програм з теми дослідження 97
4.1.1. Програма спеціального курсу «Прикладна математика для учнів 8-11 класів з поглибленим вивченням математики» 97
4.1.2. факультативна програма з математики «Економіка в задачах математики» 98
4.1.3. Програма розвитку творчого мислення учнів (Шахи, інтелектуальні ігри. Основи математичної логіки. Інтегрований курс навчання.) 98
4.2. Факультативне заняття з теорії графів для учнів 11 класу на тему: «Граф. Розв’язування задач за допомогою графа» 99
ВИСНОВКИ 106
СПИСОК ВИКОРИСТАНИХ ДЖЕРЕЛ 108
ДОДАТКИ 111