57
правок
Изменения
Нет описания правки
==Эйлеров путьОсновные определения==
{{Определение|definition=
'''Эйлеровым путем''' (англ. ''Eulerian path'') в графе называется [[Основные определения теории графов|путь]], который проходит по каждому ребру, причем ровно один раз.
}}
{{Определение|definition=
'''Эйлеров обход''' (англ. ''Eulerian circuit'') {{---}} обход графа, посещающий эйлеров путь.
}}
{{Определение|definition=
'''Эйлеров цикл''' (англ. ''Eulerian cycle'') {{---}} замкнутый эйлеров путь.
}}
{{Определение|definition=
Граф называется '''эйлеровым'''(англ. ''Eulerian graph''), если он содержит эйлеров цикл. Граф называется '''полуэйлеровым''', если он содержит эйлеров путь, но не содержит эйлеров цикл.
}}
Соединим ориентированным ребром вершину с большей входящей степенью с вершиной с большей исходящей степенью. Теперь можно найти эйлеров цикл, после чего удалить добавленное ребро. Очевидно найденный цикл станет путем.
==См. Такжетакже==
* [[Алгоритм построения Эйлерова цикла]]
