Эйлеровы графы

Автор: Пользователь скрыл имя, 19 Декабря 2011 в 14:32, курсовая работа

Краткое описание

Начало теории графов все единодушно относят к 1736 г., когда Л. Эйлер не только решил популярную в то время задачу о кенигсбергских мостах, но и нашел критерий существования в графе специального маршрута (эйлерова цикла). Вначале теория графов казалась довольно незначительным разделом математики, так как она имела дело в основном с математическими развлечениями и головоломками. Однако дальнейшее развитие математики и особенно её приложений дало сильный толчок развитию теории графов.

Оглавление

Введение 3
Основные определения и понятия. 4
Теорема Эйлера 9
Заключение

Файлы: 1 файл

Копия Курсовая работа.doc

— 103.00 Кб (Скачать)

       Содержание 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

       Введение

           Начало теории графов все единодушно относят к 1736 г., когда  Л. Эйлер не только решил популярную в то время задачу о кенигсбергских мостах, но и нашел критерий существования в графе специального маршрута (эйлерова цикла). Вначале теория графов казалась довольно незначительным разделом математики, так как она имела дело в основном с математическими развлечениями и головоломками. Однако дальнейшее развитие математики и особенно её приложений дало сильный толчок развитию теории графов.

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

           В этой работе будут  подробно рассмотрены эйлеровы графы, а также основные теоремы и  сведения, связанные с этим понятием. 
     
     
     
     
     
     
     
     
     

       Основные  определения и  понятия

       Пусть V — непустое множество, V(2) — множество всех его двухэлементных подмножеств. Пара (V, Е), где Е — произвольное подмножество множества V(2), называется графом (неориентированным графом). Элементы множества V называются вершинами графа, а элементы множества E ребрами.

         Итак, граф — это конечное множество V вершин и множество E ребер. Множества вершин и ребер графа G обозначаются символами VG и EG соответственно. Вершины и ребра графа называются его элементами. Число |VG| вершин графа G называется его порядком и обозначается через |G|. Если |G| = n, |EG| = m, то G называют (n, m)-графом.

       Говорят, что две вершины u и v графа смежны, если множество {и, v} является ребром, и не смежны в противном случае. Если e = {и, v} — ребро, то вершины u и v называют его концами. В этой ситуации говорят также, что ребро e соединяет вершины u и v. Такое ребро обозначается символом uv.

        Таким образом, два ребра называются смежными, если они имеют общий конец. Вершина u и ребро e называются инцидентными, если v является концом ребра e (т. е. e = иv), и не инцидентными в противном случае.

        Степенью вершины  vi в графе G называется число рёбер, инцидентных vi ,обозначается di.

        Маршрутом в графе  G называется чередующаяся последовательность вершин и рёбер v0,x1,v1,…vn-1,xn,vn; эта последовательность начинается и кончается вершиной, и каждое ребро последовательности инцидентно двум вершинам, одна из которых непосредственно предшествует ему, а другая непосредственно следует за ним. Указанный маршрут соединяет вершины v0 и vn и его можно обозначить v0v1v2…vn (наличие рёбер подразумевается). Эта последовательность иногда называется (v0-vn)-маршрутом. Маршрут замкнут, если v0=vn, и открыт в противном случае. Маршрут называется цепью, если все его рёбра различны, и простой цепью, если все вершины (а следовательно, и рёбра ) различны. Замкнутая цепь называется циклом. Замкнутый маршрут называется простым циклом, если все его  n вершин различны и n³3.

        Граф называется связным, если любые две его несовпадающие вершины соединены маршрутом.

        Граф H называется подграфом (или частью) графа G, если VH VG, EH EG.

        Всякий максимальный связный подграф графа G называется связной компонентой (или просто компонентой) графа G. Слово «максимальный» означает максимальный относительно включения, т. е. не содержащийся в связном подграфе с большим числом элементов.

         Задача  о  кёнигсбергских  мостах.

         Отцом теории графов является Эйлер (1707-1782), решивший в 1736г. широко известную в то время задачу, называвшуюся проблемой Кёнигсбергских мостов. В городе Кёнигсберге (ныне Калининград) было два острова, соединенных семью мостами с берегами реки Преголя и друг с другом так, как показано на рисунке 1. Задача состояла в следующем: найти маршрут прохождения всех четырёх частей суши, который начинался бы с любой из них, кончался бы на этой же части и ровно один раз проходил по каждому мосту.

         

               Рис.1.

     Легко, конечно попытаться решить эту задачу эмпирически, производя перебор всех маршрутов, но все попытки окончатся неудачей. Исключительный вклад Эйлера в решение этой задачи заключается в том, что он доказал невозможность такого маршрута.

     Для доказательства того, что задача не имеет решения, Эйлер обозначил каждую часть суши точкой (вершиной), а каждый мост – линией (ребром), соединяющей соответствующие точки. Получился “граф”. Этот граф показан на рисунке 2, где точки отмечены теми же буквами, что и четыре части суши на рисунке 1. 

           
     
     
     
     

                             Рис.2.

         Утверждение о несуществовании “положительного” решения у этой задачи эквивалентно утверждению о невозможности  обойти специальным образом граф, представленный на рисунке 2.

         Отправляясь от этого частного случая, Эйлер обобщил постановку задачи и нашёл критерий существования обхода у данного графа, а именно граф должен быть связным и каждая его вершина должна быть инцидентна чётному числу рёбер.

         Эйлеровы  графы

         Эйлер доказал неразрешимость задачи о  кёнигсбергских мостах. В своей работе, опубликованной в 1736 году, он сформулировал и решил следующую общую проблему теории графов: при каких условиях связный граф содержит цикл, проходящий через каждое его ребро?

         

                     Рис. 3.      

         Цикл  в графе называется эйлеровым, если он содержит все ребра графа. Связный граф, в котором есть эйлеров цикл, называется эйлеровым графом. Такой граф можно нарисовать, не отрывая карандаша от бумаги и не повторяя линий.

         Например, граф, изображенный на рис. 3, является эйлеровым, поскольку он содержит эйлеров цикл (1, 2, 3, 4, 5, 6, 4, 2, 6, 1). В этом графе есть и другие эйлеровы циклы. Ясно, что любые два таких цикла отличаются друг от друга только порядком обхода ребер. 
     
     
     

       Теорема Эйлера

           Связный граф является эйлеровым  тогда и только тогда, когда степени всех его вершин четны.

           Доказательство

            Необходимость. Пусть G - эйлеров граф. Эйлеров цикл этого графа, проходя через каждую его вершину, входит в нее по одному ребру, а выходит по другому. Это означает, что каждая вершина инцидентна четному числу ребер эйлерова цикла, а поскольку такой цикл содержит все ребра графа G, то отсюда следует четность степеней всех его вершин.

            Достаточность. Предположим теперь, что степени вершин графа G четны. Начнем цепь P1 из произвольной вершины v1 и будем продолжать ее, насколько возможно, выбирая каждый раз новое ребро. Так как степени всех вершин  четны,  то  попав  в  очередную  отличную  от v1 вершину, мы всегда будем иметь в распоряжении еще не пройденное ребро.  Поэтому цепь P1  можно продолжить путем добавления этого ребра. Таким образом, построение цепи P1 закончится в вершине v1, т. е. P1 непременно будет циклом. Если окажется, что P1 содержит все ребра графа G, то это будет требуемый эйлеров цикл. В противном случае, удалив из G все ребра цикла P1, рассмотрим граф G1, полученный в результате такой операции. Поскольку P1 и G имели вершины только четных степеней, то, очевидно, и G1 будет обладать тем же свойством. Кроме того, в силу связности графа G графы P1 и G1 должны иметь хотя бы одну общую вершину v2. Теперь, начиная с вершины v2, построим цикл P2 в графе G1 подобно тому, как строили цикл P1. Обозначим через P′1 и P″1 части цикла P1 от v1 до v2 и от v2 до v1 соответственно. Получим новый цикл P1, который, начиная с v1 проходит по ребрам цепи Pi до v2, затем обходит все ребра цикла P2 и, наконец, возвращается в v1 по ребрам цепи P″1 (рис. 43.5).

           Если цикл P3 не эйлеров, то проделав аналогичные построения, получим еще больший цикл и т. д. Этот процесс закончится построением эйлерова цикла.  

           Естественно   возникает   вопрос: как   найти   хотя   бы один эйлеров цикл в эйлеровом графе G, т. е. как занумеровать ребра графа числами 1, 2,...,/EG/ с тем, что бы номер, присвоенный ребру, указывал, каким по счету это ребро проходится в эйлеровом цикле? Оказывается, это можно сделать, если нумеровать ребра, придерживаясь следующих двух правил:

           1.  Начиная с  произвольной вершины и, присваиваем произвольному  ребру  uv  номер   1.   Затем  вычеркиваем ребро иv и переходим в вершину v.

           2.  Пусть w — вершина, в которую мы пришли в результате  выполнения  предыдущего  шага,  и k- номер, присвоенный некоторому ребру на этом шаге. Выбираем любое ребро, инцидентное вершине w, причем мост выбираем только в том случае, когда нет других возможностей; присваиваем выбранному ребру номер k +1 и вычеркиваем его.

           Этот процесс, называемый алгоритмом Флёри, заканчивается, когда все ребра графа вычеркнуты, т. е. занумерованы.

           Дадим теперь обоснование  алгоритма. Прежде всего заметим, что поскольку степень каждой вершины графа G четна, то алгоритм может закончить работу только в той вершине, с которой начал. Поэтому он строит некоторый цикл G, и надо только доказать, что этот цикл включает все ребра графа G. Предположим, что это не так, и пусть G' — связная компонента графа G — EC, не являющаяся изолированной вершиной. Рассмотрим множество А ребер цикла С, инцидентных вершинам, вошедшим в G'. Ясно, что А=0. Пусть а -ребро из А, получившее в процессе работы алгоритма наибольший номер, т. е. вычеркнутое последним среди ребер А. Тогда, как легко видеть, ребро а к моменту вычеркивания было мостом в графе. Однако это противоречит правилу выбора очередного ребра. 
     
     
     
     
     
     
     
     
     
     
     
     

     Заключение

     В данной работе были рассмотрены основные понятия теории графов и большое внимание уделено вопросу существования эйлеровых цепей и циклов, рассмотрена теорема Эйлера, позволяющая находить эйлеровы циклы в произвольном графе.

     Известно, что эйлеровы графы получили широкое  распространение и популярность благодаря тому, что многие головоломки  и задачи можно решить с использованием знаний теории графов. Задачи на отыскание путей через лабиринты, близкие к задачам на эйлеровы графы, находят применение в современной психологии и при конструировании вычислительных машин. Также с практической точки зрения, сейчас графы применяют во многих других областях науки таких как: программирование, физика, химия, биология, экономика и т.д.   
 
 
 
 
 
 
 
 
 

     Литература

Информация о работе Эйлеровы графы