Изменения

==Эйлеров путьОсновные определения==Путь <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'') {{---}} обход графа, посещающий эйлеров путь.}}

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

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

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

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

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

1. Все вершины имеют четную степень. 2. Все компоненты связности, кроме, может быть, одной, не содержат ребер. |proof= Необходимость мы доказали ранее. Докажем достаточность, используя индукцию по числу вершин <tex>n</tex>. База индукции: <tex>n = 0</tex> цикл существует. Предположим что граф имеющий менее <tex>n</tex> вершин содержит эйлеров цикл. Рассмотрим вершину связный граф <tex>G = (V, E)</tex> с <tex>n > 0</tex> вершинами, степени которых четны. Пусть <tex>v_1</tex> и <tex>v_2</tex> {{---}} вершины графа. Поскольку граф связный, то существует путь из <tex>v_1</tex> в <mathtex>uv_2</mathtex> со степенью больше 2. После удаления цикла Степень <mathtex>cv_2</mathtex> {{---}} чётная, значит существует неиспользованное ребро, по которому можно продолжить путь из <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</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<br/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=Добавим ребро, соединяющее вершины с нечетной степенью. Теперь можно найти эйлеров цикл, после чего удалить добавленное ребро. Очевидно найденный цикл станет путем.

====[[Основные определения теории графов|Ориентированный граф]]===={{theoremТеорема|statement=Ориентированный граф В ориентированном графе <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 Нахождение эйлерова пути]