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

Автор работы: Пользователь скрыл имя, 17 Февраля 2013 в 22:04, дипломная работа

Описание

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

Содержание

ВСТУП 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

Скачать (1.47 Мб) Сколько стоит заказать работу?

Работа состоит из 1 файл

diplomna.docx

— 1.52 Мб (Скачать документ)

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

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

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

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

Отже, практична цінність теорії графів безперечна.

Ця дипломна робота може бути використана учнями школи, вчителями та студентами математичних і природничих спеціальностей.

СПИСОК ВИКОРИСТАНИХ ДЖЕРЕЛ

Аносов Д.В. Проблемы модернизации школьного курса математики. // Математика в школе. – 2000. - №1. – С.2-4.
Асаанов М. О. Дискретная математика: графы, матроиды, алгоритмы / М. О. Асаанов, В. А. Баранский, В. В. Расин. – Ижевск: НИЦ «РХД», 2001. – 288 с.
Барболин М.П. Головоломки и графы. // Квант. – 1975. – №2. –С.59-61.
Беве Л. Любая карта может быть аскрашена в четыре цвета. // Квант. – 1977. - №1. – С.60-61.
Бекламов В.Б. Применение теоремы Эйлера к некоторым задачам. // Квант. – 1974. - №10. – С.17-19.
Березина Л.Ю. Графы и их применение: Пособие для учителей. – М.: Просвещение, 1979. – 144с.
Березина Л.Ю. О графах с цветными ребрами // Квант. – 1973. - №8. – С49-53.
Берж К. Теория графов и ее применение / М. : Изд-во иностр. лит-ры, 1962. – 316 с.
Болтянский В. Плоские графы. // Квант. – 1981. - №7. – С.11-16.
Болтянский В. Топология графов. // Квант. – 1981. - №3. – С.18-22.
Вагутен В.Н. задача о графах. // Квант. – 1974. - №11. – С.23-29.
Вакарелов Д.И. Путешествия по графам. // Квант. – 1986. – №7. – С.50-58.
Гарднер М. Математичні головоломки і розваги. – М.: Світ, 1971. – 256с.
Гарднер М. Рамсеевская теория графов. // Квант. – 1988. - №4. – С.15-20.
Глобин А.И. Методика обучения решению текстовіх алгебраических задач с применением графов (6-8 класс).: Дис. канд. пед. Наук: 13.00.02., К., 1988. – 180с.
Гроссман И., Магнус В. Группы и их графы. – М.: Мир, 1971. – 246с.
Евстигнеев В. А. Применение теории графов в програмировании / В. А. Евстигнеев. – М. : Наука, 1983. -350 с.
Єлісеєва О., Петров В. Графи працюють на нас. // Математика в школі. – 2002. - №5. – С.47-51.
Зыков А. А. Теория графов / А. А. Зыков. – М. : Наука, 1987. – 380 с.
Камерон П. Теория графов, теория кодирования и блок-схем / П. Камерон, Дж. Ван Линт. – М. : Наука, 1980. – 144 с.
Касаткін В.Н. Незвичайні задачі математики. – К.: Радянська школа, 1987. – 193с.
Киц М.Г. О плоских правильных графах. // Квант. – 1975. - №11. – С.12-16.
Концепция математического образования в 12-летней школе. // Математика (приложение к «Учительской газете»). – 2000. - №7. – С.1-5.
Кристофидес Н. Теория графов. Алгоритмический поход / Н. Кристофидес. – М. : Мир, 1978. – 432 с.
Ловас Л. Прикладные задачи теории графов. Теория паросочетаний в математике, физике, химии / Л. Ловас, М. Пламмер. – М. ; Мир, 1998. – 658 с.
Майника Э. Алгоритмы оптимизации на сетях и графах / Майника Э. – М. : Мир, 1981. – 424 с.
Мельников О. И. Занимательные задачи по теории графов / О. И. Мельников. – Минск: ТетраСистемс, 2001. – 144 с.
Оре О. Графы и их применение / О. Оре. – М. : Мир, 1965. – 174 с.
Оре О. Теория графов / О. Оре. – М. : Наука, 1980. – 336 с.
Приятель А. Решение логических задач при помощи графов с цветными ребрами. // Квант. – 1974. – №12. – С.14-22.
Саркисян А. А. познакомтесь с топологией / А. А. Саркисян, Ю. М. Колягин. - М. : Просвещение, 1976. – 79 с.
Татт У. Теория графов / У. Татт. – М. : Мир, 1988. - 324 с.
Уилсон Р. Введение в теорию графов / Р. Уилсон. – М. : Мир, 1977. – 208 с.
Фосс В. Елементы теории графов // Квант. – 1973. – №7. – С.56-59.
Футер А. Сигналы, графы и короли на торе. // Квант. – 1977. - №7. – С.14-19.
Харари Ф. Теория графов / Ф. Харари. – М. : Мир, 1973. – 300 с.

ДОДАТКИ

Додаток А

Логічна структура інтегрованого курсу

НПР	РН	ПМ
1	2	3
Методи розв’язування задач на аналіз та синтез логічних структур на основі Булевої алгебри дискретної та безперервної функції та теорії графів.	Елементи теорії графів. Основні поняття. Маршрути, ланцюги, цикли.	Моделювання за допомогою теорії графів. Графічний метод.
Сітьові графи. Метод розрахунку. Застосування графів у різних галузях знанью	2.Задачі на ланцюги, вихід із лабіринту. Гамільтонові цикли. Дерево.	2. Практичне розв’язання задач за допомогою теорії графів. Графічний метод.
Елементи комбінаторики. Засоби, що застосовуються для розв’язання практичних задач.	3.Розвиваючі задачі з елементами логіки.	3. Побудова математичних моделей комбінаторних задач.
4.Розв′язування задач на стику різних наук.	4. Методи та принципи розв′язування винахідницьких задач. Прийоми вирішення суперечностей.	4. Опрацювання статистичної вибірки деякої випадкової величини.

Информация о работе Графи та їх застосування