Изменения

==Эйлеров Основные определения=={{Определение|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. Все компоненты связности, кроме, может быть, одной, причем каждое - только один разне содержат ребер. |proof= Необходимость мы доказали ранее. Докажем достаточность, используя индукцию по числу вершин <tex>n<br/tex>.

База индукции: <tex>n ==Эйлеров 0</tex> цикл==существует.

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

'''Эквивалентно:'''Эйлеровым циклом является Эйлеров путьРассмотрим связный граф <tex>G = (V, являющийся цикломE)</tex> с <tex>n > 0</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> будет покрывать все ребра, инцидентные <mathtex>v_1</tex>. Если <tex>C_1</tex> является эйлеровым циклом для <tex>G = (V</tex>, тогда доказательство закончено. Если нет, E)то пусть <tex>G'</tex> {{---}} подграф графа <tex>G</mathtex> называется Эйлеровым, если полученный удалением всех рёбер, принадлежащих <tex>C_1</tex>. Поскольку <tex>C_1</tex> содержит Эйлеров циклчётное число рёбер, инцидентных каждой вершине, то каждая вершина подграфа <tex>G'</tex> имеет чётную степень.А так как <tex>C_1</tex> покрывает все ребра, инцидентные <tex>v_1<br/tex>, то граф <tex>G'</tex> будет состоять из нескольких компонент связности.

ГрафРассмотрим какую-либо компоненту связности <tex>G'</tex>. Поскольку рассматриваемая компонента связности <tex>G'</tex> имеет менее, чем <tex>n</tex> вершин, а у каждой вершины графа <tex>G'</tex> чётная степень, то у каждой компоненты связности <tex>G'</tex> существует эйлеров цикл. Пусть для рассматриваемой компоненты связноти это цикл <tex>C_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>a</tex>, затем пройти <tex>C_2</tex> и вернуться в <tex>a</tex>. Если новый эйлеров цикл не являющийся является эйлеровым цикломдля <tex>G</tex>, продолжаем использовать этот процесс, расширяя наш эйлеров цикл, пока, в конце концов, называют полуэйлеровым. не получим эйлеров цикл для <tex>G<br/tex>.

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

Неориентированный почти связный<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>''База:''<br/> Лес из <math>N</math> деревьевВсе компоненты слабой связности кроме, каждое из 1 вершины.<br>''Переход:''<br>Рассмотри графможет быть одной, в котором степени всех вершин четныене содержат ребер.<br/>В нем найдется простой цикл, т.к. иначе граф является лесом <math>-></math> в нем есть хотя бы два листа, что противоречит четности степеней всех вершин.<br/>|proof=Рассмотрим цикл <math>c</math> такой, что при удалении его ребер не образуется компонент связности размера больше 1Доказательство аналогично случаю неориентированного графа.<br/>Такой всегда существует, т.к. граф компонент двусвязности произвольного связного графа является деревом, а т.к. все вершины <math>G</math> <br/>}}

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

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