АкушерствоАнатомияАнестезиологияВакцинопрофилактикаВалеологияВетеринарияГигиенаЗаболеванияИммунологияКардиологияНеврологияНефрологияОнкологияОториноларингологияОфтальмологияПаразитологияПедиатрияПервая помощьПсихиатрияПульмонологияРеанимацияРевматологияСтоматологияТерапияТоксикологияТравматологияУрологияФармакологияФармацевтикаФизиотерапияФтизиатрияХирургияЭндокринологияЭпидемиология

Доказательство окончено.

Приведенное доказательство достаточности фактически содержит рекурсивный алгоритм построения цикла Эйлера в произвольном графе. Такой алгоритм основан на нахождениив этом графе элементарного цикла, длина которого больше 3. В дальнейшем выполняется рекурсивное построение циклов Эйлера в четных связных подграфах, получаемых из исходного графа после удаления ребер найденного элемеентарного цикла.

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

При этом приведенное доказательство теоремы требует незначительных уточнений в формулировках и рассуждениях.

Например, для ориентированных графов доказательство теоремы Эйлера остается справедливым, если дополнительно потребовать, чтобы число ребер, выходящих из всякой вершины, равнялось числу ребер, ведущих в эту вершину.

Для графов, допускающих петли, теорема Эйлера также имеет простое обобщение. Неориентированный связный граф имеет цикл Эйлера тогда и только тогда, когда степени вершин этого графа, через которые проходят петли, нечетные, а степени вершин, через которые не проходят петли, четные.

Чтобы доказать теорему Эйлера для случая графов, имеющих петли при первом прохождении через произвольную вершину, инцидентную петле, необходимо один раз пройти по этой петле.

Требование связности графа является существенным для существования циклов Эйлера в графах. Если это условие не выполняется, но справедливы остальные условия теоремы Эйлера, то можно утверждать, что в каждой компоненте связности графа имеется цикл Эйлера.

Упражнение. Сформулировать и доказать обобщение теоремы Эйлера на случай ориентированных графов.

Дата добавления: 2015-09-27 | Просмотры: 378 | Нарушение авторских прав