П. 4. Эйлеровы графы.

Решение.

Примеры.

Один ли граф изображен на этих рисунках?

1. Вершины одинаково обозначены, имеют одинаковые степени, следовательно, на рисунке изображен один и тот же граф.

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

Ответ: Это один и тот же граф.

3.На этом рисунке изображены два разные графа, так как у первого графа только две вершины А и В имеют степень равную 2. Во втором графе таких вершин больше.

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

Определение 24.Эйлеровым путем в графе называется путь, содержащий все ребра графа.

Определение 25.Эйлеровым циклом в графе называется цикл, содержащий все ребра графа.

Определение 26. Граф, обладающий эйлеровым циклом, называется эйлеровым графом.

Теорема 2.Если граф обладает эйлеровым циклом, то он связный.

Примеры эйлеровых графов:

1) план выставки, если экспонаты расположены по обеим сторонам залов, т.е. можно составить такой замкнутый маршрут, что по каждому залу посетитель сможет пройти в точности два раза – по одному с каждой стороны в разных направлениях.

2) Любой город можно обойти, пройдя по каждой улице ровно два раза – по одному в каждом направлении.

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

Решение.

Замечание. Способ обходить все ребра графа можно использовать, например, для отыскания пути, позволяющего выбраться из лабиринта. Если известно, что у лабиринта все «стенки» связаны друг с другом, т.е. нет замкнутых маршрутов, по которым можно возвращаться в исходную точку, то такой лабиринт всегда можно обойти весь, касаясь стенки одной рукой, например, правой.

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

Теорема 3.Для того, чтобы связный граф (мультиграф) был эйлеровым, необходимо и достаточно, чтобы степени всех его вершин были четными.

Замечание. Данная теорема позволяет решить задачу о семи кенигсбергских мостах.