Теория графов
Дипломная работа - Математика и статистика
Другие дипломы по предмету Математика и статистика
ВЫПУСКНАЯ КВАЛИФИКАЦИОННАЯ РАБОТА
Теория графов
2010 г.
СОДЕРЖАНИЕ
Введение
Глава I. Графы и их применение
1. Основные понятия теории графов
2. Расстояния в графах. Диаметр, радиус, центр графа
3. Нагруженные графы. Определение кратчайших маршрутов
4. Раскраска графов. Применение раскраски графов в практической деятельности человека
5. Эйлеровы и гамильтоновы графы
Глава II. Элементы теории графов на факультативных занятиях в школе
1. Роль факультативных занятий
2. Постановка факультатива Элементы теории графов в средней школе
Заключение
Литература
ВВЕДЕНИЕ
Что такое граф? Когда речь заходит о графе, большинство людей представляют себе график, т.е. нечто вроде диаграммы, отражающей производственную деятельность какого-нибудь предприятия (рис. 1), или гладкую кривую (рис. 2), позволяющую наглядно представить свойства какой-нибудь математической функции.
Рис. 1Рис. 2
Но для огромного (и все возрастающего) числа математиков слово граф означает нечто совсем иное.
Начало теории графов как математической дисциплине было положено Эйлером в его знаменитом рассуждении о Кёнигсбергских мостах. Однако, эта статья Эйлера 1736 года была единственной в течение почти ста лет. Интерес к проблемам теории графов возродился около середины прошлого столетия и был сосредоточен, главным образом в Англии. Имелось много причин для такого оживления изучения графов. Естественные науки оказали свое влияние на это, благодаря исследованиям электрических сетей, моделей кристаллов и структур молекул. Развития формальной логики привело к изучению бинарных отношений в форме графов. Большое число популярных головоломок поддавалось формулировкам непосредственно в терминах графов, и это приводило к пониманию, что многие задачи такого рода содержат некоторое математическое ядро, важность которого выходит за рамки конкретного вопроса. Наиболее знаменитая среди этих задач - проблема четырех красок, впервые поставленная перед математиками Де Морганом около 1850 года. Никакая другая проблема не вызывала столь многочисленных и остроумных работ в области теории графов. Благодаря своей простой формулировке и раздражающей неуловимости она до сих пор остается мощным стимулом исследований различных свойств графов.
Настоящее столетие было свидетелем неуклонного развития теории графов, которая за последние десять лет и даже двадцать вступила в новый период интенсивных разработок. В этом процессе явно заметно влияние запросов новых областей приложений: теории игр и программирования, теории передачи сообщений, электрических сетей и контактных цепей, а также проблем биологии и психологии.
Настоящая работа состоит из двух глав.
В первой главе освещаются методы теории графов. В частности, даются ключевые понятия и определения этой теории, рассматриваются различные способы представления графов, методы построения маршрутов, циклов, деревьев и раскраски графов, а также особенности применения этих методов в различных сферах.
Вторая глава включает в себя факультативный курс в старшей школе с приложением разработки факультатива.
Раздел теоретического изложения материала подкреплен практическими задачами и упражнениями.
Глава I. ГРАФЫ И ИХ ПРИМЕНЕНИЕ
1. Основные понятия теории графов
Пусть дано множество V = {v1, v2,…,vn} и пусть на множестве V определено семейство U = {u1, u2, …, un} пар элементов Uk = {vi, vj}, (k=1, m) произвольной кратности и упорядочения. Пара {V, U} называется графом. Граф, как правило, обозначают прописными латинскими буквами, например G, H. Принято также писать G (V, U) для того, чтобы определить некоторый конкретный граф G.
Элементы v1, v2,…, vn называют вершинами графа, а пары Uк = {vi, vj},
(к = 1, m) - ребрами.
Определению графа можно дать такую интерпретацию. Пусть имеем описание графа:
(V, U) = {{v1, v2,…, v6}, {{v1, v3}, , {v3, v3}}}.
Это описание можно отобразить графически, как показано на рис.3. На этом рисунке некоторые ребра отмечены стрелкой, а соответствующие им пары вершин в описании графа выделены угловыми скобками. Это связано с тем, что для некоторого произвольного ребра можно принимать или не принимать во внимание порядок расположения его концов.
Если этот порядок не существенен, то ребро называется неориентированным, в противном случае ребро называется ориентированным. Ориентированные ребра называются также дугами.
Рис. 3
Для ориентированного ребра определены понятия начальной и конечной вершины. Начальная вершина записывается в начале пары вершин, определяющих дугу, а конечная - в конце. Так, на рис.3 ребра являются дугами. Они представлены упорядоченными парами вершин и в связи с этим обозначены также, как обозначаются упорядоченные множества.
Ребра {v1, v3}, {v3, v4} неориентированы. Для любого неориентированного ребра полагают, что {vi, vj} = {vj, vi}. Ребро {vi, vi} называется петлей. На рис.3 имеем петлю {v3, v3}. Петли обычно неориентированы.
Граф, у которого все ребра неориентированы, называется неориентированным.
Граф, у которого все ребра ориентированы, называется ориентированным или орграфом.