Изменения

==Эйлеров путьОсновные определения==

[[Основные определения теории графов|Путь]] <tex>P</tex> <tex>u_0 \rightarrow u_0u_1 \rightarrow u_1 \rightarrow u_1u_2 \rightarrow ...\rightarrow u_{k-1}u_k \rightarrow u_k</tex> в [[Основные определения теории графов|графе]] <tex>G = (V, E)</tex>называется '''эйлеровымЭйлеровым путем''' (англ. ''Eulerian path'', если <tex>P</tex> содержит все ) в графе называется [[Основные определения теории графов|ребрапуть]] <tex>G</tex>, который проходит по каждому ребру, причем каждое - только ровно один раз. <br/>

[[Основные определения теории графов|Цикл]] <tex>C</tex> <tex>u_0 \rightarrow u_0u_1 \rightarrow u_1 \rightarrow u_1u_2 \rightarrow ...\rightarrow u_ku_0\rightarrow u_0</tex> в графе <tex>G = (V, E)</tex>называется '''эйлеровымЭйлеров обход''' (англ. ''Eulerian circuit'') {{---}} обход графа, если <tex>C</tex> содержит все ребра <tex>G</tex>, причем каждое - только один разпосещающий эйлеров путь. <br/>

Граф <tex>G = (V, E)</tex> называется Эйлеровым, если содержит '''Эйлеров цикл''' (англ. Граф, содержащий Эйлеров ''Eulerian cycle'') {{---}} замкнутый эйлеров путь, не являющийся циклом, называют полуэйлеровым. <br/>

===Критерий Эйлеровости==={{Определение|id = euler_graph|definition=Неориентированный граф назовем почти связнымГраф называется '''эйлеровым''' (англ. ''Eulerian graph''), если все его [[Отношение_связности,_компоненты_связности|компоненты связности]], кроме, быть может, одной, имеют размер 1он содержит эйлеров цикл.<br/>Ориентированный граф назовем почти связнымГраф называется '''полуэйлеровым''', если все его [[Отношение_связности,_компоненты_связности|компоненты слабой связности]], кроме, быть может, однойон содержит эйлеров путь, имеют размер 1но не содержит эйлеров цикл.

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

2. Если в графе существует более одной компоненты связности с ребрами, то очевидно, что нельзя пройти по их ребрам одним путем.}} [[Файл:Euler_path_1.png|160px|thumb|left|Эйлерова пути нет.<br>Количество вершин нечетной степени больше двух.]][[Файл:Euler_path_2.png|230px|thumb|none|Две компоненты связности, одна имеет ребра.]] {{Теорема|statement=В графе <tex>G = (V, E) </tex> существует эйлеров цикл тогда и только тогда, когда: 1. Все вершины имеют четную степень. 2. Все компоненты связности, кроме, может быть, одной, не содержат ребер. |proof= Необходимость мы доказали ранее. Докажем достаточность, используя индукцию по числу вершин <tex>n</tex>. База индукции: <tex>n = 0</tex> цикл существует. Предположим что граф имеющий менее <tex>n</tex> вершин содержит эйлеров цикл. Рассмотрим вершину связный граф <tex>G = (V, E)</tex> с <tex>n > 0</tex> вершинами, степени которых четны. Пусть <tex>uv_1</tex> и <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> через <tex>cv_1</tex> таким же образом, до тех пор, пока мы в очередной раз не сможем выйти из вершины <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>. Для Поскольку рассматриваемая компонента связности <tex>G - c'</tex> имеет менее, чем <tex>n</tex>вершин, по предположению индукцииа у каждой вершины графа <tex>G'</tex> чётная степень, то у каждой компоненты связности <tex>G'</tex> существует эйлеров цикл. Пусть для рассматриваемой компоненты связноти это цикл <tex>eC_2</tex>.Тогда в У <tex>C_1</tex> и <tex>C_2</tex> имеется общая вершина <tex>a</tex>, так как <tex>G</tex> тоже существует Эйлеров обход - сначала cвязен. Теперь можно обойти эйлеров цикл с, начиная с вершины его в вершине <tex>a</tex>, обойти <tex>C_1</tex> , вернуться в <tex>ua</tex>, затем обойти пройти <tex>C_2</tex> и вернуться в <tex>a</tex>. Если новый эйлеров цикл не является эйлеровым циклом для <tex>G</tex>, продолжаем использовать этот процесс, расширяя наш эйлеров цикл, пока, в конце концов, не получим эйлеров цикл для <tex>eG</tex>. }}{{Теорема|about=следствие|statement=В графе <tex>G = (V, E) <br/tex>существует эйлеров путь тогда и только тогда, когда:1. Количество вершин с нечетной степенью меньше или равно двум.Переход доказан2. Все компоненты связности кроме, может быть одной, не содержат ребер.|proof=Добавим ребро, соединяющее вершины с нечетной степенью. Теперь можно найти эйлеров цикл, после чего удалить добавленное ребро. Очевидно найденный цикл станет путем.

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

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

<br/>==См. также=='''Следствие'''<br/>Ориентированный почти связный граф <tex>G = (V, E)</tex> является полуэйлеровым тогда и только тогда, когда содержит ровно одну вершину, * [[Основные_определения_теории_графов|входная степеньАлгоритм построения Эйлерова цикла]] которой на единицу больше  == Источники информации== * Ф.Харари Теория графов. Глава 7. Обходы графов. Эйлеровы графы.* Уилсон Р. Введение в теорию графов. {{---}} М.: Мир, 1977* [[Основные_определения_теории_графов|выходной]], и ровно одну вершину, выходная степень которой на единицу больше входнойhttp://e-maxx.<brru/>algo/euler_path Нахождение эйлерова пути]

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