Изменения

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

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

Цикл <math>p</math> <math>u_0 -> u_0u_1 -> u_1 -> u_1u_2 -> ...-> u_ku_0-> u_0==Критерий эйлеровости=={{Теорема|id = eulerTheorem|statement=Для того, чтобы граф </math> в графе <mathtex>G = (V, E)</mathtex>был эйлеровым необходимо чтобы:называется ''Эйлеровым'', если содержит все ребра <math>G</math>, причем каждое - только один раз1. Все вершины имели четную степень. <br/>

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

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

Неориентированный почти связный В графе <ref name tex>G = "almost"(V, E) </tex>существует эйлеров цикл тогда и только тогда, когда: 1. Все вершины имеют четную степень.Неориентированный граф назовем почти связным, если все его 2. Все компоненты связности, кроме, может быть может, одной, имеют размер 1не содержат ребер. |proof= Необходимость мы доказали ранее.Докажем достаточность, используя индукцию по числу вершин <tex>n<br/tex>. Ориентированный граф назовем почти связным, если все его компоненты слабой связности, кроме, быть может, одной, имеют размер 1База индукции: <tex>n = 0</tex> цикл существует. Предположим что граф имеющий менее <tex>n</reftex> вершин содержит эйлеров цикл. Рассмотрим связный граф <mathtex>G = (V, E)</mathtex> с <tex>n > 0</tex> является Эйлеровым тогда и только тогдавершинами, когда не содержит вершин нечетной степеникоторых четны. Пусть <tex>v_1<br/tex> и <tex>|proof='''Достаточность:'''v_2<br/tex>Рассмотрим Эйлеров цикл {{---}} вершины графа. Поскольку граф связный, то существует путь из <mathtex>pv_1</mathtex> в <mathtex>v_2</tex>. Степень <tex>v_2</tex> {{---}} чётная, значит существует неиспользованное ребро, по которому можно продолжить путь из <tex>Gv_2</mathtex>.Каждое вхождение вершины Так как граф конечный, то путь, в конце концов, должен вернуться в <tex>v_1</tex>, следовательно мы получим замкнутый путь (цикл(кроме первого и последнего вхождения начальной вершины) добавляет 2 к ее степени.Назовем этот цикл <tex>C_1</tex>. Будем продолжать строить <tex>C_1</tex> через <tex>v_1<br/tex>Для начальной таким же образом, до тех пор, пока мы в очередной раз не сможем выйти из вершины ее первое и последнее вхождение также суммарно добавляют 2 к ее степени<tex>v_1</tex>, то есть <tex>C_1</tex> будет покрывать все ребра, инцидентные <tex>v_1</tex>.Если <tex>C_1<br/tex> является эйлеровым циклом для <tex>G<br/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'<br/tex>Докажем утверждение по индукции.Поскольку рассматриваемая компонента связности <brtex>''База:'G'<br/tex> Лес из имеет менее, чем <mathtex>Nn</mathtex> деревьеввершин, каждое из 1 а у каждой вершины.графа <brtex>''Переход:'G'<br/tex>Рассмотри графчётная степень, в котором степени всех вершин четные.то у каждой компоненты связности <tex>G'<br/tex>В нем найдется простой существует эйлеров цикл, т.кПусть для рассматриваемой компоненты связноти это цикл <tex>C_2</tex>. иначе граф является лесом, У <tex>C_1</tex> и тогда в нем есть хотя бы два листа<tex>C_2</tex> имеется общая вершина <tex>a</tex>, что противоречит четности степеней всех вершинтак как <tex>G</tex> cвязен.Рассмотрим Теперь можно обойти эйлеров цикл , начиная его в вершине <mathtex>ca</mathtex> такой, что при удалении его ребер не образуется компонент связности размера больше 1.Такой всегда существуетобойти <tex>C_1</tex> , вернуться в <tex>a</tex>, тзатем пройти <tex>C_2</tex> и вернуться в <tex>a</tex>.к. граф компонент двусвязности произвольного связного графа Если новый эйлеров цикл не является деревом, а т.к. все вершины эйлеровым циклом для <mathtex>G</mathtex>, продолжаем использовать этот процесс, расширяя наш эйлеров цикл, пока, в конце концов, не получим эйлеров цикл для <tex> G<br/tex>.

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

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

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