Выпускная квалификационная работа теория графов
 Скачать 0.56 Mb.
|
|
ВЫПУСКНАЯ КВАЛИФИКАЦИОННАЯ РАБОТА Теория графов 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}, Это описание можно отобразить графически, как показано на рис.3. На этом рисунке некоторые ребра отмечены стрелкой, а соответствующие им пары вершин в описании графа выделены угловыми скобками. Это связано с тем, что для некоторого произвольного ребра можно принимать или не принимать во внимание порядок расположения его концов. Если этот порядок не существенен, то ребро называется неориентированным, в противном случае ребро называется ориентированным. Ориентированные ребра называются также дугами. Рис. 3 Для ориентированного ребра определены понятия начальной и конечной вершины. Начальная вершина записывается в начале пары вершин, определяющих дугу, а конечная - в конце. Так, на рис.3 ребра <v5, v1> и <v2, v3> являются дугами. Они представлены упорядоченными парами вершин и в связи с этим обозначены также, как обозначаются упорядоченные множества. Ребра {v1, v3}, {v3, v4} неориентированы. Для любого неориентированного ребра полагают, что {vi, vj} = {vj, vi}. Ребро {vi, vi} называется петлей. На рис.3 имеем петлю {v3, v3}. Петли обычно неориентированы. Граф, у которого все ребра неориентированы, называется неориентированным. Граф, у которого все ребра ориентированы, называется ориентированным или орграфом. Иногда удобно преобразовывать неориентированный граф в ориентированный - заменой каждого неориентированного ребра парой ориентированных ребер с противоположной ориентацией. На рис.3 приведен смешанный граф, т.е. содержащий как ориентированные, так и неориентированные ребра и петлю. Некоторые вершину графа G могут не войти в список пар. Такие вершины называются изолированными. В рассмотренном примере это вершина v6. Граф, у которого все вершины изолированы, называется нуль-графом. Множество ребер такого графа пусто. Антиподом нуль-графа является полный граф. Ребрами полного графа являются все возможные пары его вершин. Как в случае ориентированного графа, так и в случае неориентированного, говорят, что ребро инцидентно паре определяющих его вершин. Одной и той же паре вершин можно поставить в соответствии множество инцидентных ребер. Такие ребра называются кранными. Так, на рис.4 представлены различные пары вершин (vi, vj), инцидентных трем различным ребрам u1, u2, u3. Одно из них направлено, а два - нет. Рис. 4 Граф называется плоским, если он может быть изображен на плоскости так, что все пересечения ребер есть его вершины. Так, граф приведенный на рис.3, плоским не является, а на рис.4 - плоский. Если граф G представлен конечным множеством ребер, то он называется конечным, независимо от числа вершин. В противном случае - бесконечный. Граф Н называется частью графа G или частичным графом Н С G, если множество его вершин V (G) графа G и все ребра U являются ребрами G. Частным, но важным типом частичных графов являются подграфы. Пусть А - подмножество множества вершин V графа G. Подграф G (A) графа G есть такая часть графа, множеством вершин которого является А, а ребрами - все ребра из G, оба конца которых лежат в А. Для любой части G графа определена дополнительная часть G (дополнение), состоящая из всех тех ребер, которые не принадлежат G, и всех инцидентных им вершин. Например, граф G на рис.5 неполный. А проведенные недостающие ребра составляют граф дополнение G рис.6. Рис. 5 Рис. 6 Вершины в графе могут отличаться друг от друга тем, скольким ребрам они принадлежат. Степенью вершины называется число ребер графа, которым принадлежит эта вершина. Обозначать степени вершин v1, v2, v3 будем так: δ (v1), δ (v2), δ (v3) и т.п. У графа на рис.7 δ (v1) = 1; δ (v2) = 2. У графа на рис. 8 степени всех вершин равны нулю. Рис. 7 Рис. 8 При решении задач и доказательстве теорем использовались разные способы задания графов. На рисунках граф изображался с помощью точек (крутков, квадратиков) и отрезков, соединяющих пары точек. Можно граф представить специальной таблицей. Пользуются еще матричным представлением графа. Выбирают то представление или способ, который удобнее и нагляднее при рассмотрении конкретного вопроса. Наиболее известный и популярный способ представления графов состоит в геометрическом изображении точек (вершин) и линий (ребер) на бумаге. При численном решении задач на вычислительных машинах граф должен быть представлен дискретным способом. Существует довольно много способов такого рода представления графов. Однако простота использования представления графа, как и эффективность алгоритма, в основе которого он лежит, в полной мере зависит от конкретного выбора этого представления. Одно из направлений теории графов связано с их матричным представлением. Существуют различные виды матриц, ассоциированные с графами. Эти алгебраические формы используются для решения многих задач теории графов. Ниже рассматриваются две такие матричные формы и несколько нестандартных представлений, которые наиболее широко используются в алгоритмах на графах. Пусть имеем граф G (V, U). Его матрицей смежности называется квадратная матрица (аi, j) порядка n2, где n - число вершин, а аi, j - число ребер, инцидентных вершинам vi и vj. Если граф не имеет кратных ребер, то аi, j = 1, когда vi и vj смежные, и аi, j = 0, когда vi и vj не смежные. Если граф не имеет петель, то все его диагональные элементы равны нулю. Рассмотрим примеры. На рис. 9 изображены три неориентированных графа. В первом случае (рис.9а) имеем граф без петель и без кратных ребер. Во втором случае (рис.9б) имеем кратные ребра. В третьем случае (рис.9в) в вершинах v1 и v4 имеются петли. а б в Рис. 9 Соответствующие этим трем случаям матрицы смежности представлены ниже: а)  б)  в)  Для неориентированного графа матрица смежности является симметрической. Для ориентированного графа матрица смежности симметрической, вообще говоря, не является. Матрицей инциденций неориентированного графа, называется матрица (bi,j) размера n · m, где n - число вершин, а m - число ребер, построенная по правилу  Соответствующие рис.9б матрицы инциденций представлены ниже.  Примечание: для графа на рис. 9б приняты следующие обозначения ребер: Х1 = (v1, v2)1, Х2 = (v1, v2)2, Х3 = (v1, v4)1, Х4 = (v1, v4)2, Х5 = (v1, v4)3, Х6 = (v2, v4), Х7 = (v3, v2). Матрица инциденций неориентированного графа обладает следующими очевидными свойствами: ) в графе без петель каждый столбец этой матрицы имеет в точности две единицы, соответствующие паре вершин ребра; ) если в графе имеются петли, то в столбцах, соответствующих петлям, имеется по одной единице, а в остальных - по две. Матрицей инциденций ориентированного графа называется матрица (bi, j) размера n · m, где n - число вершин, а m - число ребер, построенная по правилу  Рассмотрим, например, граф, изображенный на рис.10. Рис. 10 Построенная в соответствии с описанным правилом матрица инциденций этого графа имеет вид  Примечание: для графа на рис.10 приняты следующие обозначения дуг: Х1 = (v1, v2), Х2 = (v1, v3), Х3 = (v3, v2), Х4 = (v3, v4), Х5 = (v5, v4), Х6 = (v5, v6), Х7 = (v6, v5). Ориентированный граф, как правило, петель не содержит. Его матрица инциденций имеет в каждом столбце +1 и -1, которые отвечают началу и концу каждого ребра. Задачи, возникающие на практике, приводят к разного вида операциям над матрицами. Рассмотрим некоторые из них. Пусть система авиалиний между городами Х1, Х2, Х3 одной страны и городами У1 и У2 другой страны задается подмножеством пар: (Х1, У1), (Х1, У2), (Х2, У1), (Х2, У2), (Х3, У2), т.е. множеством ребер соответствующего графа. Система связи между этими же городами водным транспортом задается другим подмножеством пар: (Х1, У1), (Х2, У1), (Х2, У2), (Х3, У1). Кроме этого, для каждой пары городов (Хi, Уj). Известно число различных водных и авиамаршрутов. Эти числа можно проставить над ребрами на рисунке графа или зафиксировать с помощью двух матриц одинакового порядка: У1 У2 У1 У2 Х1 4 1 Х1 2 0 А = Х2 2 6 В = Х2 1 3 Х3 0 4 Х3 2 0 Требуется определить, сколькими различными способами с помощью воздушного или водного транспорта можно попасть из каждого города одной страны в каждый город другой страны. Естественно, что для этого достаточно сложить соответствующие элементы матриц А и В. Ответ можно записать с помощью новой матрицы того же порядка: У1 У2 Х1 6 1 С = Х2 3 9 Х3 2 4 В общем случае операцию сложения двух матриц можно записать так: если А = (аi,j) и В = (bi,j) - матрицы одного порядка, то матрица С = А + В = (Сi,j), где Сi,j = аi,j + bi,j. Рассмотрим еще одну задачу. Пусть в каких-то трех странах выделены некоторые города, связанные с транспортом четырех видов: воздушным, железнодорожным, водным и автобусным. Схема транспортных связей между городами Х1 и Х2, принадлежащими первой стране, и городами У1, У2, У3, принадлежащими второй стране, зафиксирована матрицей А, где аi,j показывает на число видов транспорта, соединяющих города Хi и Уi. Аналогичная схема транспортных связей между городами У1, У2, У3, принадлежащими второй стране, и городами Z1, Z2, принадлежащим третьей стране, представлена матрицей В. Какие конкретно виды транспорта связывают пары городов, нас не интересует. Города первой и третьей стран непосредственных связей не имеют. У1 У2 У3 Z1 Z2 А = Х1 4 0 2 У1 2 1 Х2 2 3 1 В = У2 0 3 У3 3 0 Требуется подсчитать число различных маршрутов от каждого из городов первой страны в каждый из городов третьей страны, проходящих через вторую страну. Если нарисовать соответствующую схему, то решить задачу не трудно, попробуем решить матричным методом. Таким образом, по заданным матрицам А и В требуется определить элементы сi,j матрицы С: 1 Z2 C = Х1 С11 С12 Х2 С21 С22 Рассуждения определяют матрицу С и алгоритм нахождения элементов сi,j, а именно Z1 Z2 C = Х1 (а11в11 + а12в21 + а13в31 а11в12 + а12в22 + а13в32 Х2 (а21в11 + а22в21 + а23в31 а21в12 + а22в22 + а23в32 Z1 Z2 C = Х1 14 4 Х2 7 11 Рассмотренная задача убеждает в целесообразности введения еще одной операции над матрицами. Эту операцию принято называть операцией умножения матриц. Если С = АВ, то элементы матрицы С определяются следующей формулой: сi,j = ai1в1j + ai2в2j + ai3в3j + … + ainвnj Таким образом, элемент сi,j образуется из элементов i-й строки матрицы А и элементов j-го столбца матрицы В. Следует обратить внимание на следующие два факта: ) операция умножения матрицы А на матрицу В определена только в том случае, если число столбцов в матрице А равно числу строк в матрице В. ) если матрица А имеет порядок (m x n), а матрица В - порядок (n x r), то матрица - произведение С = АВ имеет порядок (n x m). Рассмотрим некоторые основные операции, производимые над графами. Операцией добавления к графу G = <V, U> вершины а образуется граф <V u {a}, U>. Операцией добавления дуги (а, в) к графу G состоит в образовании графа <V u {a, в), U u {(а, в)}>. При операции удаления дуги, получаем <V, U \ {(а, в)}>. Операции удаления вершины заключается в удалении вершины Vi вместе с инцидентными ей дугами: <V\{Vi}, U \ {(Vj Vk) Vj = Vi или Vk = Vi}>. Операция отождествления вершин (в случае, когда Vi и Vj соединены дугой, операцию называют стягиванием дуги (ViVj). Пример: |