Изменения

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

{{Определение|definition=='''Эйлеров цикл==''' (англ. ''Eulerian cycle'') {{---}} замкнутый эйлеров путь.}}

Цикл <math>p</math> <math>u_0 -> u_0u_1 -> u_1 -> u_1u_2 -> ...-> u_ku_0-> u_0</math> в графе <math>G {{Определение|id = euler_graph|definition= Граф называется '''эйлеровым''' (Vангл. ''Eulerian graph''), E)</math> <br/>если он содержит эйлеров цикл. Граф называется ''Эйлеровым'полуэйлеровым''', если он содержит все ребра <math>G</math>эйлеров путь, причем каждое - только один разно не содержит эйлеров цикл. <br/>}}

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

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

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

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

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

====[[Основные определения теории графов|Ориентированный граф]]====

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