Изменения

==Эйлеров Основные определения=={{Определение|definition='''Эйлеровым путем''' (англ. ''Eulerian path'') в графе называется [[Основные определения теории графов|путь=]], который проходит по каждому ребру, причем ровно один раз.}} {{Определение|definition=Путь <math>p</math> <math>u_0 '''Эйлеров обход''' (англ. ''Eulerian circuit'') {{-> u_0u_1 -> u_1 -> u_1u_2 -> }} обход графа, посещающий эйлеров путь.}} {{Определение|definition='''Эйлеров цикл''' (англ.''Eulerian cycle'') {{---}} замкнутый эйлеров путь.-> u_}} {{Определение|id = euler_graph|definition=Граф называется '''эйлеровым''' (k-1англ. ''Eulerian graph'')u_k -> u_k</math> в графе , если он содержит эйлеров цикл. Граф называется '''полуэйлеровым''', если он содержит эйлеров путь, но не содержит эйлеров цикл.}} ==Критерий эйлеровости=={{Теорема|id = eulerTheorem|statement=Для того, чтобы граф <mathtex>G = (V, E)</mathtex> был эйлеровым необходимо чтобы:1. Все вершины имели четную степень. 2. Все компоненты связности, кроме, может быть, одной, не содержали ребер.|proof=1. Допустим в графе существует вершина с нечетной степенью. Рассмотрим эйлеров обход графа. Заметим, что при попадании в вершину и при выходе из нее мы уменьшаем ее степень на два (помечаем уже пройденые ребра), если эта вершина не является стартовой(она же конечная для цикла). Для стартовой(конечной) вершины мы уменьшаем ее степень на один в начале обхода эйлерова цикла, и на один при завершении. Следовательно вершин с нечетной степенью быть не может. Наше предположение неверно. 2. Если в графе существует более одной компоненты связности с ребрами, то очевидно, что нельзя пройти по их ребрам одним путем.}} [[Файл:Euler_path_1.png|160px|thumb|left|Эйлерова пути нет.<br/>Количество вершин нечетной степени больше двух.]]называется ''Эйлеровым''[[Файл:Euler_path_2.png|230px|thumb|none|Две компоненты связности, если содержит все одна имеет ребра .]] {{Теорема|statement=В графе <mathtex>G= (V, E) </mathtex>существует эйлеров цикл тогда и только тогда, когда: 1. Все вершины имеют четную степень. 2. Все компоненты связности, причем каждое - только один разкроме, может быть, одной, не содержат ребер. <br/> |proof=

Цикл База индукции: <mathtex>p</math> <math>u_0 -> u_0u_1 -> u_1 -> u_1u_2 -> ...-> u_ku_0-> u_0</math> в графе <math>G n = (V, E)</math> 0<br/tex>называется ''Эйлеровым'', если содержит все ребра <math>G</math>, причем каждое - только один разцикл существует. <br/>

'''Эквивалентно:'''Эйлеровым циклом является Эйлеров путь, являющийся цикломПредположим что граф имеющий менее <tex>n</tex> вершин содержит эйлеров цикл.

==Эйлеров Рассмотрим связный граф=====Определение===Граф <mathtex>G = (V, E)</mathtex> с <tex>n > называется Эйлеровым, если содержит Эйлеров цикл.0<br/tex>вершинами, степени которых четны.

ГрафПусть <tex>v_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>. Будем продолжать строить <tex>C_1</tex> через <tex>v_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<br/tex>содержит чётное число рёбер, инцидентных каждой вершине, то каждая вершина подграфа <tex>G'</tex> имеет чётную степень. А так как <tex>C_1</tex> покрывает все ребра, инцидентные <tex>v_1</tex>, то граф <tex>G'</tex> будет состоять из нескольких компонент связности.

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

Рассмотрим вершину <math>u</math> со степенью больше 2. После удаления цикла <math>c</math> из графа степени всех вершин останутся четными,<br/> ====[[Основные определения теории графов|Ориентированный граф]]===={{Теорема|statement=при этом количество ребер в В ориентированном графе уменьшится. Для <mathtex>G - c= (V, E) </mathtex>, по предположению индукции, существует эйлеров цикл <math>e</math>тогда и только тогда, когда: 1. Входная степень любой вершины равна ее выходной степени.<br/>Тогда в <math>G</math> тоже существует Эйлеров обход - сначала обойти цикл с2. Все компоненты слабой связности кроме, начиная с вершины <math>u</math>может быть одной, затем обойти <math>e</math>не содержат ребер.|proof=Доказательство аналогично случаю неориентированного графа.<br/>

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

==Источники информации==Ориентированный граф===='''Теорема'''<br/>Ориентированный граф <math>G = (V, E) </math> является Эйлеровым тогда и только тогда, входная степень любой вершины равна ее выходной степени.<br/><br/>'''Доказательство'''<br/>Достаточность:<br/>Необходимость:<br/>

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