Содержание 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

       Введение

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

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

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

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

       Пусть V — непустое множество, V⁽²⁾ — множество всех его двухэлементных подмножеств. Пара (V, Е), где Е — произвольное подмножество множества V⁽²⁾, называется графом (неориентированным графом). Элементы множества 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), и не инцидентными в противном случае.

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

        Маршрутом в графе  G называется чередующаяся последовательность вершин и рёбер v₀,x₁,v₁,…v_n-1,x_n,v_n; эта последовательность начинается и кончается вершиной, и каждое ребро последовательности инцидентно двум вершинам, одна из которых непосредственно предшествует ему, а другая непосредственно следует за ним. Указанный маршрут соединяет вершины v₀ и v_n и его можно обозначить v₀v₁v₂…v_n (наличие рёбер подразумевается). Эта последовательность иногда называется (v₀-v_n)-маршрутом. Маршрут замкнут, если v₀=v_n, и открыт в противном случае. Маршрут называется цепью, если все его рёбра различны, и простой цепью, если все вершины (а следовательно, и рёбра ) различны. Замкнутая цепь называется циклом. Замкнутый маршрут называется простым циклом, если все его  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 четны. Начнем цепь P₁ из произвольной вершины v₁ и будем продолжать ее, насколько возможно, выбирая каждый раз новое ребро. Так как степени всех вершин  четны,  то  попав  в  очередную  отличную  от v₁ вершину, мы всегда будем иметь в распоряжении еще не пройденное ребро.  Поэтому цепь P₁  можно продолжить путем добавления этого ребра. Таким образом, построение цепи P₁ закончится в вершине v₁, т. е. P₁ непременно будет циклом. Если окажется, что P₁ содержит все ребра графа G, то это будет требуемый эйлеров цикл. В противном случае, удалив из G все ребра цикла P₁, рассмотрим граф G₁, полученный в результате такой операции. Поскольку P₁ и G имели вершины только четных степеней, то, очевидно, и G₁ будет обладать тем же свойством. Кроме того, в силу связности графа G графы P₁ и G₁ должны иметь хотя бы одну общую вершину v₂. Теперь, начиная с вершины v₂, построим цикл P₂ в графе G₁ подобно тому, как строили цикл P₁. Обозначим через P′₁ и P″₁ части цикла P₁ от v₁ до v₂ и от v₂ до v₁ соответственно. Получим новый цикл P₁, который, начиная с v₁ проходит по ребрам цепи P_i до v₂, затем обходит все ребра цикла P₂ и, наконец, возвращается в v₁ по ребрам цепи P″₁ (рис. 43.5).

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

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

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

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

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

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

     Заключение

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

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

     Литература