74. Теорема Эйлера.

Теорема:

Граф называется Эйлоровым тогда и только тогда, когда он является связным и степени всех его вершин являются четными.

Необходимость:

В несвязанном графе каждый цикл принадлежит какой-либо его мвязанной части, т.е. не проходит через все его ребра (кроме случая, когда все компоненты связности графа, кроме одной, - изолированные вершины). Кроме того, каждый раз, когда эйлеров цикл приходит в какую-нибудь вершину, он должен выйти из нее по другому ребру, т.е. инцидентные вершинам ребра можно разбить на пары соседних в эйлеровом цикле. Исключением являются ребра, инцидентные началу эйлерова цикла, совпадающему с его концом. Сначала цикл выходит из этой вершины по какому-либо ребру. Затем он, возможно, несколько раз возвращается в эту вершину, каждый раз входя по новому ребру и выходя так же по новому, но другому ребру. В конце концов он возвращается в исходную вершину по не затронутому ранее ребру. Таким образом, и в этом случае инцидентные этой вершине ребра также распадаются на пары соседних в эйлеровом цикле, но одна из этих пар состоит из ребра, проходимого в начале процесса, и другого, замыкающего этот процесс.

Достаточность:

Пусть G – конечный связный граф с четными степенями всех вершин. Начнем построение эйлерова цикла с поизвольной вершины v графа G. каждый раз, когда мы добавляем к маршруту новое ребро и приходим в новую вершину, число свободных ребер в этой вершине изменяется на единицу. Если до этого оно было четным, то теперь оно становится нечетным и не может оказаться нулем. После ухода из этой вершины число свободных инцидентных ей ребер уменьшается еще на 1 и вновь становиться четным. Исключением является свободная вершина, у которой после начала процесса число свободных ребер нечетно и остается нечетным после каждого возвращения в эту вершину и ухода из нее.

Описанный ранее процесс построения цикла может закончиться лишь в той вершине, откуда он начинался, но при этом не обязательно, чтобы он проходил через все ребра графа. Принадлежащие ему ребра порождают связную часть P графа G, в которой степени всех вершин четны. Значит, они четны и для разности G\P. Так как граф G связен, в дополнении G\P существует хотя бы одна вершина v, принадлежащая также части Р. Начиная с этой вершины, можно провести, как и ранее, построение цикла Р в G\P, кончающегося в вершине v.

Эта вершина, кроме того, разбивает цикл Р на два участка Р₁ с началом v и концом v и Р₂ с началом v и концом v. Тогда Р₁РР₂ – также цикл, начинающийся в вершине v, но имеющий большее число ребер. Если и этот цикл не проходит через все ребра, этот процесс расширения цикла можно повторить. Каждый раз число ребер в цикле увеличивается не менее чем на два, значит, в конце концов эйлеров цикл будет построен.

75. Эйлеровы цепи.

Так называется цепь, включающая все ребра данного конечного неориентированного графа G, но имеющая различные начало v и конец v. Чтобы в графе существовала эйлерова цепь, необходимы его связность и четность всех вершин, кроме начальной v и конечной v. Последние две вершины должны иметь нечетные степени: из v мы лишний раз выходим, а в v лишний раз входим. Эти условия достаточны для существования эйлеровой цепи. Можно искать наименьшее число не пересекающихся по ребрам цепей, покрывающих конечный связный граф G. Пусть G не является эйлеровы графом, k – число его вершин нечетной степени. Каждая вершина нечетной степени должна быть концом хотя бы одной из покрывающих цепей. Следовательно, число последних не меньше, чем k/2. Но ограничиться k/2 цепями не так трудно. Соединим вершины нечетной степени попарно k/2 ребрами произвольным образом. Тогда степень каждой их этих вершин увеличится на единицу и станет четной. Получится эйлеров граф, в котором существует эйлеров цикл. Выбросим теперь обратно присоединенные ребра. При выбрасывании первого ребра эйлеров цикл превратиться в эйлорову цепь, а при выбрасывании каждой следующей цепи одна из возникших к этому моменту цепей разобъется на 2 части. Таким образом, общее число этих цепей станет k/2. При построении никогда не выбрасываются соседние по эйлерову циклу ребра.