Изменения

==Эйлеров путьОсновные определения=={{Определение|definition='''Эйлеровым путем''' (англ. ''Eulerian path'') в графе называется [[Основные определения теории графов|Путьпуть]] <math>p</math> <math>u_0 -> u_0u_1 -> u_1 -> u_1u_2 -> ., который проходит по каждому ребру, причем ровно один раз.}} {{Определение|definition='''Эйлеров обход''' (англ.''Eulerian circuit'') {{-> u</math>_{<math>k-1</math>} <math>u_k -> u_k</math> в [[Основные определения теории графов}} обход графа, посещающий эйлеров путь.}} {{Определение|графе]] <math>G definition= '''Эйлеров цикл''' (V, E)</math>называется англ. ''ЭйлеровымEulerian cycle'', если содержит все [[Основные определения теории графов|ребра]] <math>G</math>, причем каждое ) {{--- только один раз}} замкнутый эйлеров путь. <br/>}}

{{Определение|id =euler_graph|definition=Эйлеров Граф называется '''эйлеровым''' (англ. ''Eulerian graph''), если он содержит эйлеров цикл==. Граф называется '''полуэйлеровым''', если он содержит эйлеров путь, но не содержит эйлеров цикл.}}

[[Основные определения теории графов==Критерий эйлеровости=={{Теорема|Цикл]] <math>pid = eulerTheorem|statement=Для того, чтобы граф </math> <math>u_0 -> u_0u_1 -> u_1 -> u_1u_2 -> ...-> u_ku_0-> u_0</math> в графе <mathtex>G = (V, E)</mathtex>был эйлеровым необходимо чтобы:называется ''Эйлеровым'', если содержит все ребра <math>G</math>, причем каждое - только один раз1. Все вершины имели четную степень. <br/>

'''Эквивалентно:'''2. Все компоненты связности, кроме, может быть, одной, не содержали ребер.Эйлеровым циклом |proof=1. Допустим в графе существует вершина с нечетной степенью. Рассмотрим эйлеров обход графа. Заметим, что при попадании в вершину и при выходе из нее мы уменьшаем ее степень на два (помечаем уже пройденые ребра), если эта вершина не является Эйлеров путьстартовой(она же конечная для цикла). Для стартовой(конечной) вершины мы уменьшаем ее степень на один в начале обхода эйлерова цикла, являющийся цикломи на один при завершении. Следовательно вершин с нечетной степенью быть не может. Наше предположение неверно.

==Эйлеров граф=====Определение===Граф <math>G = (V, E)</math> называется Эйлеровым, если содержит Эйлеров цикл2. ГрафЕсли в графе существует более одной компоненты связности с ребрами, содержащий Эйлеров путьто очевидно, не являющийся циклом, называют полуэйлеровымчто нельзя пройти по их ребрам одним путем. <br/>}}

===Критерий Эйлеровости===[[Файл:Euler_path_1.png|160px|thumb|left|Эйлерова пути нет.<br>Количество вершин нечетной степени больше двух.]]====[[Основные определения теории графовФайл:Euler_path_2.png|230px|thumb|none|Неориентированный графДве компоненты связности, одна имеет ребра.]]====

Неориентированный почти связный <ref name = "almost">Неориентированный граф назовем почти связным, если все его [[Отношение_связности,_компоненты_связности|компоненты связности]], кроме, быть может, одной, имеют размер 1.В графе <br/>Ориентированный граф назовем почти связным, если все его [[Отношение_связности,_компоненты_связности|компоненты слабой связности]], кроме, быть может, одной, имеют размер 1.</ref> граф <mathtex>G = (V, E)</mathtex> является Эйлеровым существует эйлеров цикл тогда и только тогда, когда не содержит вершин нечетной [[Основные определения теории графов|степени]].<br/>|proof='''Достаточность:'''<br/>Рассмотрим Эйлеров цикл <math>p</math> в <math>G</math>1.Каждое вхождение Все вершины в цикл(кроме первого и последнего вхождения начальной вершины) добавляет 2 к ее степени.<br/>Для начальной вершины ее первое и последнее вхождение также суммарно добавляют 2 к ее степени. В итоге, каждая вершина имеет имеют четную степень.<br/>'''Необходимость:'''<br/>Докажем утверждение по индукции2.<br><br/>''База:''<br/> Лес из <math>N</math> деревьевВсе компоненты связности, кроме, может быть, одной, каждое из 1 вершиныне содержат ребер.<br/><br/>''Переход:''<br/>Рассмотри граф, в котором степени всех вершин четные.<br/>В нем найдется простой цикл, т.к. иначе граф является [[Дерево, эквивалентные определения|лесом]], и тогда в нем есть хотя бы два листа, что противоречит четности степеней всех вершин.proof=Рассмотрим цикл <math>c</math> такой, что при удалении его ребер не образуется двух компонент связности размера больше 1.Такой всегда существует, тНеобходимость мы доказали ранее.к. [[Граф_блоков-точек_сочленения|граф блоков и точек сочленения]] произвольного почти связного графа является [[ДеревоДокажем достаточность, эквивалентные определения|деревом]], а т.к. все вершины используя индукцию по числу вершин <mathtex>Gn</mathtex> имеют четные степени, то не могут являться в нем листами. Значит, листами в дереве блоков и точек сочленения такого графа будут циклы, а в любом цикле есть подмножество, являющееся простым циклом.

База индукции: <tex>n = 0</tex> цикл существует. Предположим что граф имеющий менее <tex>n</tex> вершин содержит эйлеров цикл. Рассмотрим вершину связный граф <mathtex>uG = (V, E)</tex> с <tex>n > 0</tex> вершинами, степени которых четны. Пусть <tex>v_1</mathtex> и <tex>v_2</tex> {{---}} вершины графа. Поскольку граф связный, то существует путь из <tex>v_1</tex> в <tex>v_2</tex>. Степень <tex>v_2</tex> {{---}} чётная, значит существует неиспользованное ребро, по которому можно продолжить путь из <tex>v_2</tex>. Так как граф конечный, то путь, в конце концов, должен вернуться в <tex>v_1</tex>, следовательно мы получим замкнутый путь (цикл). Назовем этот цикл <tex>C_1</tex> со степенью больше 2. После удаления цикла Будем продолжать строить <tex>C_1</tex> через <mathtex>cv_1</mathtex> таким же образом, до тех пор, пока мы в очередной раз не сможем выйти из вершины <tex>v_1</tex>, то есть <tex>C_1</tex> будет покрывать все ребра, инцидентные <tex>v_1</tex>. Если <tex>C_1</tex> является эйлеровым циклом для <tex>G</tex>, тогда доказательство закончено. Если нет, то пусть <tex>G'</tex> {{---}} подграф графа степени <tex>G</tex>, полученный удалением всех вершин останутся четнымирёбер, принадлежащих <tex>C_1</tex>. Поскольку <tex>C_1</tex> содержит чётное число рёбер, инцидентных каждой вершине, то каждая вершина подграфа <tex>G'</tex> имеет чётную степень. А так как <tex>C_1</tex> покрывает все ребра, инцидентные <tex>v_1</tex>,то граф <tex>G'</tex> будет состоять из нескольких компонент связности.при этом количество ребер в графе уменьшитсяРассмотрим какую-либо компоненту связности <tex>G'</tex>. Для Поскольку рассматриваемая компонента связности <mathtex>G - c'</tex> имеет менее, чем <tex>n</mathtex>вершин, по предположению индукцииа у каждой вершины графа <tex>G'</tex> чётная степень, то у каждой компоненты связности <tex>G'</tex> существует эйлеров цикл. Пусть для рассматриваемой компоненты связноти это цикл <mathtex>eC_2</mathtex>.Тогда в У <tex>C_1</tex> и <tex>C_2</tex> имеется общая вершина <tex>a</tex>, так как <mathtex>G</mathtex> тоже существует Эйлеров обход - сначала cвязен. Теперь можно обойти эйлеров цикл с, начиная с вершины его в вершине <tex>a</tex>, обойти <tex>C_1</tex> , вернуться в <mathtex>ua</mathtex>, затем обойти пройти <tex>C_2</tex> и вернуться в <tex>a</tex>. Если новый эйлеров цикл не является эйлеровым циклом для <tex>G</tex>, продолжаем использовать этот процесс, расширяя наш эйлеров цикл, пока, в конце концов, не получим эйлеров цикл для <mathtex>eG</mathtex>. }}{{Теорема|about=следствие|statement=В графе <tex>G = (V, E) <br/tex>существует эйлеров путь тогда и только тогда, когда:1. Количество вершин с нечетной степенью меньше или равно двум.2. Все компоненты связности кроме, может быть одной, не содержат ребер.|proof=Переход доказанДобавим ребро, соединяющее вершины с нечетной степенью. Теперь можно найти эйлеров цикл, после чего удалить добавленное ребро. Очевидно найденный цикл станет путем.

Ориентированный почти связныйВ ориентированном графе <ref name = "almost"/> граф <mathtex>G = (V, E) </mathtex> является Эйлеровым существует эйлеров цикл тогда и только тогда, когда входная : 1. Входная степень любой вершины равна ее выходной степени.<br/> 2. Все компоненты слабой связности кроме, может быть одной, не содержат ребер.

Аналогично неориентированному графуДоказательство аналогично случаю неориентированного графа.

{{Теорема|about=cледствие|statement=В ориентированном графе <br/tex>'''Следствие'''G = (V, E)<br/tex>существует эйлеров путь если:Ориентированный почти связный1. Входная степень любой вершины равна ее выходной степени, кроме двух вершин графа, для одной из которых <ref name tex>\operatorname{deg}^+ - \operatorname{deg}^- = "almost"1</tex> граф , а для другой <mathtex>G \operatorname{deg}^+ - \operatorname{deg}^- = (V, E)-1</mathtex> является полуэйлеровым тогда и только тогда.2. Все компоненты слабой связности кроме, когда содержит ровно одну может быть одной, не содержат ребер.|proof=Соединим ориентированным ребром вершинус большей входящей степенью с вершиной с большей исходящей степенью. Теперь можно найти эйлеров цикл, после чего удалить добавленное ребро. Очевидно найденный цикл станет путем.}} ==См. также== * [[Основные_определения_теории_графов|входная степеньАлгоритм построения Эйлерова цикла]] которой на единицу больше [[Основные_определения_теории_графов|выходной]], и ровно одну вершину, выходная степень которой на единицу больше входной.<br/> == Источники информации==

== Примечания ==* Ф.Харари Теория графов. Глава 7. Обходы графов. Эйлеровы графы.<references* Уилсон Р. Введение в теорию графов. {{---}} М.: Мир, 1977* [http://e-maxx.ru/algo/>euler_path Нахождение эйлерова пути]

==Источники==[[Категория: Алгоритмы и структуры данных]]1. Ф.Харари. Теория [[Категория: Обходы графов. Москва, издательство "Едиториал УРСС". 2003 г.]][[Категория: Эйлеровы графы]]