Эйлеровы графы

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

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

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

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

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

Рисунок графа, обладающего эйлеровым путем или эйлеровым цик­лом, является уникурсальной линией.

Докажем следующие две теоремы.

Теорема 1. Если граф G(V, Е) обладает эйлеровым циклом, то он связный и все его вершины четные.

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

Д

Теорема 2. Если граф G(V,E) связный и все его вершины четные, то он обладает эйлеровым циклом.

оказательство. Если начать путь из произвольной вершины графа G(V, Е), то найдется цикл, содержащий все ребра графа. Пусть г_г — произ­вольная вершина. Из к, начнем путь по I по одному из ребер и продолжим его, проходя каждый раз по новому ребру. Все вершины графа имеют чет­ные степени, поэтому если I есть «выход» из к,, то должен быть и «вход» в Vi, также как и для любой другой вершины. И если есть «вход» в верши­ну, то должен быть и «выход». Так как число ребер конечно, то этот путь

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

Для построения эйлерова цикла в связном графе со всеми вершинами четной степени применяется следующий алгоритм:

1. Выйти из произвольной вершины о, . Каждое пройденное ребро за­черкнуть. Если путь /] замыкается в v, и проходит через все ребра графа, то получим искомый эйлеров цикл.

2. Если остались непройденные ребра, то должна существовать вер­шина г>2, принадлежащая 1\ и ребру, не вошедшему в 1\.

3. Так как г>2 — четная, то число ребер, которым принадлежит г>2 и которые не вошли в путь 1\, тоже четно. Начнем новый путь /2 из г>2 и используем только ребра, не принадлежащие 1\. Этот путь кончится в (;₂-

4. Объединим теперь оба цикла: из о, пройдем по пути 1\ к иг, затем по I2 и, вернувшись в V2, пройдем по оставшейся части 1\ обратно в Vt.

5. Если снова найдутся ребра, которые не вошли в путь, то найдем новые циклы. Так как число ребер и вершин конечно, то процесс закон­чится.

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

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