Курсовая работа: Эйлеровы графы
Первая работа по теории графов, принадлежащая известному швейцарскому математику Л.Эйлеру, появилась в 1736г. Вначале теория графов казалась довольно незначительным разделом математики, так как она имела дело в основном с математическими развлечениями и головоломками.
Дата добавления на сайт: 08 февраля 2025
МИНИСТЕРСТВО ОБРАЗОВАНИЯ РЕСПУБЛИКИ БЕЛАРУСЬ
Учреждение образования
«Брестский государственный университет имени А. С. Пушкина»
Физико-математический факультет
Кафедра алгебры, геометрии и математического моделирования
Курсовая работа
Эйлеровы графы
Левчук Ирина Юрьевна,
студентка 4 курса специальности «Математика. Информатика»
Грицук Дмитрий Владимирович - старший преподаватель кафедры алгебры, геометрии и математического моделирования, кандидат
физ.-мат. Наук
Брест 2015
СОДЕРЖАНИЕ
ВВЕДЕНИЕ
. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ
.1 Понятие графа
.1.1Определение понятия графа
.1.2 Основные понятия, связанные с графом
.1.3 Примеры графов
.2 Эйлеров и полуэйлеров графы
.2.1 Определение эйлерова и полуэйлерова графа. Примеры
.2.2 Решение задачи Эйлера о семи кёнигсбергских мостах
.2.3 Необходимые и достаточные условия для эйлеровых и полуэйлеровых графов
. ПРИМЕНЕНИЕ ТЕОРИИ ГРАФОВ К РЕШЕНИЮ ЗАДАЧ ПО МАТЕМАТИКЕ
.1 Понятие графа
.2 Степени вершин и подсчёт рёбер графа
.3 Связность графа
2.4 Графы Эйлера
ЗАКЛЮЧЕНИЕ
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ
граф эйлер ребро вершина
ВВЕДЕНИЕ
Первая работа по теории графов, принадлежащая известному швейцарскому математику Л.Эйлеру, появилась в 1736г. Вначале теория графов казалась довольно незначительным разделом математики, так как она имела дело в основном с математическими развлечениями и головоломками. Однако дальнейшее развитие математики и особенно её приложений дало сильный толчок развитию теории графов. Уже в XIX столетии графы использовались при построении схем.
Решение многих математических задач упрощается, если удается использовать графы. Представление данных в виде графа придает им наглядность и простоту.
Многие математические доказательства также упрощаются, приобретают убедительность, если пользоваться графами.
Примерами графов могут служить схема метрополитена, схемы железных или шоссейных дорог, структурные формулы молекул, планы выставок и т. д., словом, схемы и планы (или карты) без указания масштабов, показывающие лишь связи между принадлежащими им объектами.
В настоящее время теория графов находит многочисленное применение в разнообразных практических вопросах: при установлении разного рода соответствий, при решении транспортных задач, задач о потоках в сети нефтепроводов, в программировании и теории игр, теории передачи сообщений. Теория графов теперь применяется и в таких областях, как экономика, психология и биология.
Цель работы: изучение эйлеровых графов и ихприменение к решению задач по математике.
В этой работе мы познакомимся с понятием графа, подробнее рассмотрим эйлеровы графы, основные сведения и теоремы, связанные с этим понятием. А также задачи, которые решаются с помощью графов, в частности, эйлеровых.
Тема работы актуальна, так как полученные знания могут использоваться при решении олимпиадных задач, а также задач, предлагаемых в математических конкурсах.
. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ
.1 Понятие графа
.1.1 Определение графа
Дадим сначала определение простого графа G.
Определение.Пара (V(G), E(G)) называется простым графом, если(G) - непустое конечное множество элементов, называемых вершинами (или узлами, или точками), а E(G) - конечное множество неупорядоченных пар различныхэлементов из V(G), называемых рёбрами (или линиями).
Иногда V(G) называют множеством вершин, а E(G) - множеством рёбер графа G. Например, на рис. 1.1 изображён простой граф G, у которого множеством вершин V(G) является множество {u, v, w, z}, а множество рёбер E(G) состоит из пар {u, v}, {v, w}, {u, w} и {w, z}. Говорят, что ребро {u, w} соединяет вершины uи w. Так как E(G) является множеством, то в простом графе данную пару вершин может соединять не более чем одно ребро.
Рисунок 1.1
В то же время, две вершины могут быть соединены более чем одним ребром. Кроме того, часто бывает удобно снять ограничения, состоящее в том, что ребро должно соединять две различные вершины, и допустить существование петель, то есть рёбер, соединяющих вершину с ней самой. Получающийся при этом объект, в котором могут быть петли и кратные рёбра, называется общим графом, или просто графом (рис. 1.2). Подчеркнём тот факт, что каждый простой граф является графом, но не каждый граф является простым графом.
Рисунок 1.2
Более точно, графом G называется пара (V(G), E(G)), где V(G)-непустое конечное множество элементов, называемых вершинами, а E(G) - конечное семейство неупорядоченных пар элементов из V(G) (не обязательно различных), называемых рёбрами. Заметим, что употребление слова «семейство» говорит о том, что допускаются кратные рёбра. Будем называть V(G)множеством вершин, а E(G) - семейством рёбер графа G; на рис. 1.2 V(G) - это множество {u, v, w, z}, а E(G)- это семейство, состоящее из рёбер {u, v}, {v, v}, {v, v}, {v, w}, {v, w}, {v, w}, {u, w}, {u, w} и {w, z}. О каждом ребре вида {v, w} говорят, что оно соединяет вершины vиw; значит, каждая петля {v, v} соединяет вершину vсаму с собой.
Предметом изучения в теории графов являются также ориентированные графы (называемые иногда орграфами или сетями).
Определение. Орграфом D называется пара (V(D), A(D)), где V(D) - непустое конечное множество элементов, называемых вершинами, а A(D) - конечное семейство упорядоченных пар элементов из V(D), называемых дугами (или ориентированными рёбрами).
Определение. Дуга, у которой вершина v является первым элементом, а вершина w - вторым, называется дугой из v в w и обозначается (v, w).
Заметим, что дуги (v, w) и (w, v) различны. На рис. 1.3 изображён орграф, дугами которого являются (u, v), (v, v), (v, w), (v, w), (w, v), (w, u)и (w, z); порядок вершин на дуге указан стрелкой.
Рисунок 1.3
.1.2 Основные понятия, связанные с графом
Определение. Две вершины v и w графа G называются смежными, если существует соединяющее их ребро (то есть ребро вида {v, w}); при этом вершины v и w называются инцидентными этому ребру (а ребро - инцидентным эти вершинам).
Определение.Два различных ребра графа G называются смежными, если они имеют по крайней мере одну общую вершину.
Определение.Степенью (или валентностью) вершины v графа G называется число рёбер, инцидентных v.
Степень вершины v обозначается через d(v). Если вершине vинцидентна петля, то принято считать, что при подсчёте степени этой вершины петля даёт две единицы. Вершина степени 0 называется изолированной вершиной, вершина степени 1 называется висячей (или концевой) вершиной. Так, граф, изображённый на рис. 1.2, имеет одну висячую вершину, одну вершину степени 3, одну - степени 6 и одну - степени 8.
Легко видеть, что если сложить степени всех вершин графа, то получится чётное число - равное удвоенному числу рёбер, так как каждое ребро участвует в этой сумме ровно два раза. Этот результат, известный ещё двести лет назад Эйлеру, часто называют леммой о рукопожатиях.
Из неё следует, что если несколько человек обменялись рукопожатиями, то общее число пожатых рук обязательно чётно, ибо в каждом рукопожатии участвует две руки (при этом каждая рука считается столько раз, сколько она участвовала в рукопожатиях). Из леммы о рукопожатиях сразу следует, что в любом графе число вершин нечётной степени должно быть чётным.
Определение.Два графа и называются изоморфными, если существует взаимно однозначное соответствие между множествами их вершин, обладающее тем свойством, что число рёбер соединяющих любые две вершины в , равное числу рёбер, соединяющих соответствующие вершины в .
Так, два графа, изображённые на рис. 1.4, изоморфны при соответствии ↔ l, v ↔ m, w ↔ n, x ↔ p, y ↔ q, z ↔ r. Заметим, что эти графы имеют по шесть вершин - другие точки пересечения рёбер вершинами не являются.
Определение.Подграфом графа G называется граф, все вершины которого принадлежат V(G), а все рёбра принадлежат E(G).
Рисунок 1.4
Определение.Маршрутом в данном графе G называется конечная последовательность рёбер вида {, }, {, }, …, {, } (обозначаемая также через → →→ …→ ).
Определение.Маршрут называется цепью, если все его рёбра различны, и простой цепью, если все вершины ,, …, различны (кроме, может быть, = ).
Цепь или простая цепь замкнуты, если =.
Определение.Замкнутая простая цепь, содержащая по крайней мере одно ребро, называется циклом.
В частности, любая петля или любая пара кратных рёбер образует цикл.
Определение.Граф G называется связным, если для любых двух его вершин v и w существует простая цепь из v в w.
Любой граф можно разбить на непересекающиеся связные подграфы, называемые компонентами (связности), задав следующее отношение эквивалентности на множестве его вершин: две вершины эквивалентны (или связны), если существует простая цепь из одной в другую. Очевидно, что связный граф состоит из одной компоненты.
Определение.Граф называется несвязным, если число его компонент больше единицы.
.1.3 Примеры графов
Вполне несвязные графы
Определение.Граф, у которого множество рёбер пусто, называется вполне несвязным (или пустым) графом.
Будем обозначать вполне несвязный граф с nвершинами через ; показан на рис. 1.5. Заметим, что у вполне несвязного графа все вершины изолированы. Вполне несвязные графы не представляют особого интереса.
Рисунок 1.5
Полные графы
Определение.Простой граф, в котором любые две вершины смежны, называется полным графом.
Полный граф с n вершинами обозначается через . Графы и изображены на рис. 1.6 и 1.7.
Рисунок 1.6 Рисунок 1.7
Регулярные графы
Определение.Граф, у которого все вершины имеют одну и ту же степень, называется регулярным графом.
Если степень каждой вершины равна r, то граф называется регулярным степени r. Регулярные графы степени 3 называются кубическими (или трёхвалентными) графами. Отметим, что каждый вполне несвязный граф является регулярным степени 0, а каждый полный граф - регулярным степени n-1.
Платоновы графы
Среди регулярных графов особенно интересны так называемые платоновы графы - графы, образованные вершинами и рёбрами пяти правильных многогранников - платоновых тел: тетраэдра, куба, октаэдра и икосаэдра. Граф соответствует тетраэдру (рис. 1.6); графы, соответствующие кубу и октаэдру, показаны на рис. 1.8 и 1.9.
Рисунок 1.8
Рисунок 1.9 Рисунок 1.10
Двудольные графы
Допустим, что множество вершин графа можно разбить на два непересекающихся подмножества и так, что каждое ребро в G соединяет какую-нибудь вершину из с какой-нибудь вершиной из (рис. 1.10); тогда G называется двудольным графом. Такие графы иногда обозначают G(, ), если хотят выделить два указанных подмножества. Следует подчеркнуть, что в двудольном графе совсем не обязательно каждая вершина из соединена с каждой вершиной из ; если же это так и если при этом граф G простой, то он называется полным двудольным графом и обычно обозначается , где m и n - число вершин соответственно в и . Например, на рис. 1.11 изображён граф . Заметим, что граф имеет ровно m+nвершин и mn рёбер.
Рисунок 1.11
Связные графы
Почти все графы, рассмотренные до сих пор, состояли «из одного куска». Исключением были вполне несвязные графы (n ≥ 2) и объединения графов, состоящие из «не соединённых друг с другом частей». Формализуем это различие, называя граф связным, если его нельзя представить в виде объединения двух графов, и несвязным в противном случае. Очевидно, что всякий несвязный граф Gможно представить в виде объединения конечного числа связных графов - каждый из таких связных графов называется компонентой (связности) графа G. На рис. 1.12 изображён граф с тремя компонентами.
Рисунок 1.12
Дополнение простого графа
Пусть G - простой граф с множеством вершин V(G).
Определение. Дополнениемграфа G называется простой граф с множеством вершин V(G), в котором две вершины смежные тогда и только тогда, когда они смежны в G.
Отсюда следует, что если граф Gсодержит nвершин, то граф можно построить, удалив из графа все рёбра, принадлежащие G(здесь G считается подграфом). Заметим, что дополнение полного графа является вполне несвязным графом и наоборот; дополнение регулярного графа регулярно.
.2 Эйлеров и полуэйлеров графы
.2.1 Определение эйлерова и полуэйлерова графа. Примеры
Определение.Связный граф G называется эйлеровым, если существует замкнутая цепь, проходящая через каждое его ребро; такая цепь называется эйлеровой цепью.
Отметим, что в этом определении требуется, чтобы каждое ребро проходилось только один раз. Если снять ограничение на замкнутость цепи, то граф называется полуэйлеровым; при этом каждый граф будет полуэйлеровым. На рис. 1.13 и 1.14 изображены соответственно полуэйлеров и эйлеров графы. Заметим, что предположение о связности графа Gвведено только ради удобства, так как оно позволяет не рассматривать тривиальный случай графа, содержащего несколько изолированных вершин.
Рисунок 1.13 Рисунок 1.14
.2.2 Решение задачи Эйлера о семи кёнигсбергских мостах
Начало теории графов как раздела математики связывают с так называемой задачей о кёнигсбергских мостах. Эта знаменитая в своё время задача состоит в следующем.
Семь мостов города Кёнигсберга (ныне Калининград) были расположены на реке Прегольтак, как изображено на рис. 1.15. Спрашивается, можно ли, выйдя из дома, вернуться обратно, пройдя в точности один раз по каждому мосту?
Сопоставим плану города граф G, вершины которого соответствуют четырём разделяемым рекой участкам суши A, B, Cи D, а рёбра - мостам. Этот граф изображён на рис. 1.16.
Рисунок 1.15Рисунок 1.16
Эйлер доказал неразрешимость задачи о кёнигсбергских мостах. В своей работе, опубликованной в 1736 году, он сформулировал и решил следующую общую проблему теории графов: при каких условиях связный граф содержит цикл, проходящий через каждое его ребро?
Цикл в графе называется эйлеровым, если он содержит все рёбра графа. Связный граф, в котором есть эйлеров цикл, называется эйлеровым графом. Такой граф можно нарисовать, не отрывая карандаша от бумаги и не повторяя линий.
Например, граф, изображённый на рис. 1.17, является эйлеровым, поскольку он содержит эйлеров цикл (1, 2, 3, 4, 5, 6, 4, 2, 6, 1). В этом графе есть и другие эйлеровы циклы. Ясно, что любые два таких цикла отличаются друг от друга только порядком обхода рёбер.
Помимо задачи о кёнигсбергских мостах известен ряд других старинных занимательных задач (головоломок), решение которых сводится к выяснению вопроса «является ли граф эйлеровым?». В одной из них требуется обрисовать фигуру, именуемую саблями (знаком) Магомета (рис. 1.18), не отрывая карандаша от бумаги и не повторяя линий.
Рисунок 1.17Рисунок 1.18
.2.3Необходимые и достаточные условия для эйлеровых и полуэйлеровых графов
Возникает вопрос: можно ли найти необходимые и достаточные условия для того, чтобы граф был эйлеровым? Прежде чем дать полный ответ на вопрос в теореме 1, докажем простую лемму.
Лемма.Если степень каждой вершины графа G не меньше двух, то G содержит цикл.
Доказательство. Если в графе G имеются петли или кратные рёбра, то утверждение очевидно; поэтому предположим, что Gявляется простым графом. Пусть v - произвольная вершина графа G; построим по индукции маршрут
→→→ … , выбирая вершину смежной вершине , а для i ≥ 1 - выбирая смежной и отличной от (существование такой вершины гарантировано условием леммы). Так как Gимеет конечное число вершин, то в конце концов мы придём к вершине, которая уже была выбрана раньше. Предположим, что - первая такая вершина; тогда часть маршрута, лежащая между двумя вхождениями , и является требуемым циклом.
Теорема 1.Связный граф G является эйлеровым тогда и только тогда, когда каждая вершина в G имеет чётную степень.
Доказательство. =>Предположим, что Pявляется эйлеровой цепью в графе G. Тогда при всяком прохождении цепи Pчерез любую из вершин графа степень этой вершины увеличивается на два. А так как каждое ребро встречается в Pровно один раз, то каждая вершина должна иметь чётную степень.
3х = 200, чего не может быть при натуральном х. Значит, 100 дорог в таком государстве быть не может.
№10
Докажите, что число людей, живших когда-либо на Земле и сделавших нечётное число рукопожатий, чётно.
Доказательство.Сделаем всех людей, когда-либо живших на Земле, вершинами графа, а рукопожатия - его ребрами. (При этом две вершины могут соединяться и несколькими ребрами; такие ребра называют кратными.) Люди, сделавшие нечетное число рукопожатий, - нечетные вершины такого графа, поэтому по теореме о чётности числа нечётных вершин графа их количество четно.
.3 Связность графа
В стране Семёрка 15 городов, каждый из городов соединён дорогами не менее, чем с семью другими. Докажите, что из каждого города можно добраться в любой город.
Доказательство. Рассмотрим два города и пусть они не соединены путём. Так как каждый соединён не менее, чем с 7 другими, при этом города различны (если 2 совпадают, то есть путь, соединяющий исходные города), то мы указали не менее 16 городов.
№12
В Тридевятом царстве лишь один вид транспорта - ковёр-самолёт. Из столицы выходит 21 ковролиния, из города Дальний - одна, а из всех остальных городов - по 20. Докажите, что из столицы можно долететь в Дальний (возможно, с пересадками).
Доказательство. Понятно, что если нарисовать граф ковролиний Царства, то он может быть несвязным. Рассмотрим компоненту связности, которая включает в себя столицу Царства. Из столицы выходит 21 ковролиния, а из любых других городов, кроме города Дальний - по 20, поэтому, чтобы выполнялся закон о чётном числе нечётных вершин необходимо, чтобы и город Дальний входил в эту же самую компоненту связности. А так как компонента связности - связный граф, то из столицы существует путь по ковролиниям до города Дальний, что и требовалось доказать.
№13
В стране из каждого города выходит 100 дорог и от любого города можно добраться до любого другого. Одну дорогу закрыли на ремонт. Докажите, что и теперь от любого города можно добраться до любого другого.
Доказательство. Если закрыта дорога АВ, то докажем, что можно добраться из А в В. Если это не так, то в компоненте связности, содержащей А, все вершины, кроме А - чётные. Противоречие с тем, что число нечётных вершин любого графа чётно.
.4 Графы Эйлера
№14
Можно ли нарисовать граф, изображённый а) на рисунке 2.10, а; б) на рисунке 2.10, б, не отрывая карандаш от бумаги и проводя каждое ребро ровно один раз?
Ответ. а) Можно. б) Нельзя. Рисуя граф в каждую вершину, за исключением начальной и конечной, мы войдём столько же раз, сколько выйдем из неё. Поэтому степени всех вершин должны быть чётными.
Рисунок 2.10
№15
Имеется группа островов, соединённых мостами так, что от каждого острова можно добраться до любого другого. Турист обошёл все острова, пройдя по каждому мосту ровно один раз. На острове Троекратном он побывал трижды. Сколько мостов ведёт с Троекратного, если турист а) не с него начал и не на нём закончил? б) с него начал, но не на нём закончил? в) с него начал и на нём закончил?
Решение.а) на Троекратный турист 3 раза зашёл и 3 раза из него вышел, то есть использовал 6 мостов, б) в этом случае турист зашел на остров дважды, а вышел трижды, в) 4.
№16
Хулиган Вася решил прогуляться по парку и его окрестностям (см. рис. 2.11), так, чтобы при этом перелезть через каждый забор ровно один раз. Сможет ли он это сделать?
Ответ. Нет.
Рисунок 2.11
№17
а) Дан кусок проволоки длиной 120 см. Можно ли, не ломая проволоки, изготовить каркас куба ребром 10 см? б) Какое наименьшее число раз придётся ломать проволоку, чтобы изготовить требуемый каркас? в) Жук ползёт по рёбрам куба. Сможет ли он последовательно обойти все 12 рёбер куба, не пройдя дважды по одному ребру?
Ответ. а), в) Нет. Если это возможно, то ясно, что проволока идёт по рёбрам куба без наложения, то есть мы как бы нарисовали каркас куба, не отрывая карандаша от бумаги. Но это невозможно, так как у куба 8 нечётных вершин, б) Поскольку нечётных вершин 8, то таких кусков нужно не менее четырёх.
№18
На рис. 2.12 - план подвала из 10 комнат. Можно ли пройти через все двери всех комнат, запирая каждый раз ту дверь, через которую Вы проходите? С какой комнаты надо начинать движение?
Решение. Можно, так как есть лишь две комнаты с нечётным числом дверей - 8 и 10, с одной из которых и надо начинать.
Рисунок 2.12
№19
Как соединить 50 городов наименьшим числом авиалиний так, чтобы из любого города можно было попасть в любой город, сделав не более двух пересадок?
Решение. Ровно один город должен быть пересадочным, а так как в связном графе с 50 вершинами рёбер не меньше 49, то 49 - наименьшее число авиалиний.
№20
Можно ли составить решётку на рис. 2.13 а) из пяти ломаных длины 8; б) из восьми ломаных длины 5? (Длины сторон клеток равны 1.)
Ответ. а) Нельзя. Никакие две ломаные не должны иметь общих отрезков. Поэтому 12 узлов решётки, расположенных на границе квадрата и отличных от его вершины, должны быть концами ломаных, а у 5 ломаных всего 10 концов. б) Можно.
Рисунок 2.13
№21
На плоскости дано 100 окружностей, составляющих связную (не распадающуюся на части) фигуру. Доказать, что эту фигуру можно нарисовать, не отрывая карандаша от бумаги и не проводя дважды одну и ту же линию.
Доказательство. Граф связен, степени его вершин чётны.
№22
Можно ли, не отрывая карандаш от бумаги и не проводя по одной линии дважды, нарисовать: а) квадрат с диагоналями; б) правильный пятиугольник с диагоналями?
Ответ. а) Нельзя. б) Можно.
№23
Турист обошёл 6 улиц одного города, пройдя каждую ровно 2 раза, но не смог обойти их, пройдя каждую по одному разу. Могли ли так быть, если а) улицы могут оканчиваться тупиком; б) конец каждой улицы - перекрёсток?
Ответ. а) Да. Например, все улицы прямые и выходят из одной точки. б) Да. Например, 3 улицы образуют правильный треугольник, и ещё 3 улицы соединяют центр треугольника с его вершинами (теорема Эйлера).
№24
Все города страны, кроме столицы, расположены вдоль шоссе. Из столицы в каждый город ведёт прямая дорога. Две компании хотят приватизировать дороги и участки шоссе так, чтобы каждая компания могла проехать из любого города в любой другой только по своим дорогам. Смогут ли они это сделать при каком-нибудь числе городов, больше одного?
Решение. Не смогут. Допустим, что это возможно. Пусть на шоссе nгородов, тогда всего 2n-1 дорог. Поскольку дороги одной компании соединяют все города в связное множество, то этих дорог не меньше n. Тогда дорог двух компаний не меньше 2n. Противоречие.
ЗАКЛЮЧЕНИЕ
В данной работе рассмотрены основные понятия теории графов, их виды и примеры. Большое внимание уделено эйлеровым графам, рассмотрена теорема Эйлера и её доказательство, задача о кёнигсбергских мостах. В практической части показано применение теории графов к решению математических задач.
Известно, что эйлеровы графы получили широкое распространение и популярность благодаря тому, что многие головоломки и задачи можно решить с использованием знаний теории графов. Задачи, решенные с помощью графов, обладают рядом достоинств. Они развивают воображение и логическое мышление, позволяют упростить их решение.Частные примеры таких головоломок и сюжетных задач были приведены в практической части.
Также с практической точки зрения, сейчас графы применяют во многих других областях науки таких как: программирование, физика, химия, биология, экономика и т.д.
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ
Уилсон Р. Введение в теорию графов. - М.: Мир, 1977.- 207 с.
Емеличев В.А. Лекции по теории графов. - М.: Наука, 1990.- 384 с.
Горбачев Н.В. Сборник олимпиадных задач по математике. - М.: МЦНМО, 2004. - 560 с.
Голованёва Л.В. Графы. Применение графов к решению задач // Первое сентября [сайт]. Режим доступа: http://www.festival.1september.ru/. - Дата доступа : 5.05.2015.