На рис. 6 схематически изображена карта города Кенигсберга, относящаяся к XVIII в. Город был расположен на берегах и двух островах реки Преголи. Острова между собой и с берегами были связаны семью мостами. Жители города любили размышлять над проблемой: можно ли, выйдя из дома, вернуться обратно, пройдя по каждому мосту только один раз?
Полностью неориентированный граф , отвечающий задаче, представлен на рис. 7. Вершины соответствуют правому и левому берегам реки, вершины - островам, ребра графа — мостам. На языке графов, задача формулируется следующим образом: существует ли в графе простой цикл, содержащий все ребра (эйлеров цикл).
Л. Эйлер сформулировал и доказал необходимое и достаточное условие того, чтобы в произвольном полностью неориентированном связном графе существовал эйлеров цикл.
Теорема 1: Эйлеров цикл в симметрическом связном графе существует тогда и только тогда, когда степени всех его вершин — четные числа.
Доказательство: Необходимость условия теоремы очевидна, поскольку при каждом проходе через вершину, используются ровно два ребра.
|
|
Достаточность можно доказать индукцией по числу ребер графа. При числе ребер, равном двум, как нетрудно видеть, теорема справедлива. Пусть утверждение теоремы верно для всех графов с числом ребер, непревосходящем числа . Для графа с числом ребер рассмотрим произвольный простой цикл. Хотя бы один такой цикл обязательно существует для графов с четными степенями вершин. Если в графе не имеется ни одного простого цикла, то любое его ребро — перешеек. Удаляя какое-либо ребро графа, инцидентное, скажем, вершинам и , разбиваем граф на две компоненты связности. Каждое ребро в этих компонентах связности — также перешеек. После удаления ребра степени вершин и стали нечетными. Склеим компоненты связности по вершинам , и . Новая вершина, как и все остальные, в полученном связном графе имеет четную степень. Число ребер в получившемся графе равно . По предположению индукции в нем существует эйлеров цикл. Но это противоречит предположению, что в каждой компоненте связности все ребра — перешейки. Если рассматриваемый простой цикл содержит все ребра, то теорема доказана. В противном случае найдутся вершины , принадлежащие парам смежных ребер цикла, такие, что из каждой исходит по крайней мере одно ребро, не входящее в построенный цикл. В силу условия теоремы число ребер, исходящих из вершины и не принадлежащих циклу , обязательно четно.
Например, в графе, изображенном на рис. 8,:имеем:
где есть вершины , , .
Рассмотрим подграф графа , построенный с помощью ребер, не входящих в цикл . Подграф состоит, быть может, из нескольких компонент связности. Степени всех вершин — четные числа. Каждая компонента связности подграфа удовлетворяет предположению индукции, так как содержит меньше, чем ребро. Следовательно, в каждой компоненте существует; эйлеров цикл, содержащий, по крайней мере, одну из вершин . Присоединяя к циклу эйлеровы циклы подграфов , получаем эйлеров цикл графа .
|
|