Метод Флёри построения эйлерова цикла

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

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

Замечание. Граф G =(X, V) задается множеством X своих вершин и набором реберных окрестностей всех его вершин S (x)={ v |ребро v инцидентно вершине х }.

Шаг 1. Выбрать произвольную вершину х ₀Î X и положить х= x ₀, z = х ₀, С = x ₀, D = x ₀, где С - чередующаяся последовательность вершин и ребер, представляющая строящийся эйлеров цикл; D - чередующаяся последовательность, представляющая начальный отрезок цикла, который будет присоединен к текущему циклу С; х - конечная вершина в последовательности D; z - вершина на цикле С, которая служит началом D.

Шаг 2. В множестве S (x) \ [ V (С) È V (D)] выбрать произвольное ребро 1. Если S (x)=Æ, то прейти к шагу 5. Здесь V (С) и V (D) обозначают множество ребер из С и D.

Шаг 3. К D дописать ребро 1 и его конец у, т.е. положить D = D, 1, у.

Шаг 4. Положить х = у и перейти к шагу 2.

Шаг 5. Присоединить к С в вершине z цикл D, т.е. положить C = C [ x ₀, z), D, C (z, x ₀], где C [ x ₀, z) - начальный отрезок последовательности С до веpшины z, не включая z; C (z, x ₀] – отрезок последовательности С от z до x ₀, не включая z.

Шаг 6. Просматривая последовательность С слева направо, ищем первую такую вершину v, что S (v)\ V (C)=Æ. Если такой вершины нет, то перейти к шагу 8, иначе перейти к шагу 7.

Шаг 7. Положить x = v, z = v, D = v и перейти к шагу 2.

Шаг 8. Выдатьпоследовательность С, которая является эйлеровым циклом.

 

Гамильтоновы циклы

Определение: Путь, проходящий через все вершины графа (в точности по одному разу через каждую), называется гамильтоновым путем. Если начальная вершина и конечная вершина этого пути совпадают, то такой путь называется гамильтоновым контуром.

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

Рис. 3

На рис. 3 а) не гамильтонов граф; б) полугамильтонов граф; в) гамильтонов граф.

Утверждения: Пусть G - данный неорграф, a L (G) - его реберный граф, тогда:

1. а) если G имеет эйлеров цикл, то L (G) имеет как эйлеров так и гамильтонов циклы;

б) если G имеет гамильтонов цикл, то L (G) также имеет гамильтонов цикл.

2. Сильно связный полный граф гамильтонов.

3. Пусть G - сильно связный граф на n вершинах без параллельных дуг и петель. Если для любой вершины х справедливо неравенство d ^-(х)+ d ⁺(х)³ n, то граф G имеет гамильтонов контур.

4. Если орграф G полный, то он имеет ориентированный гамильтонов путь.

 

Контрольные вопросы:

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

2. Гамильтоновы графы.

3. Решить задачи:

 

1. С помощью алгоритма Флери найдите эйлерову цепь в графе:

2. Можно ли ходом шахматного коня обойти шахматную доску размером 8*8 так, чтобы каждый ход встречался ровно один раз (при этом мы считаем, что ход встречался, если конь переместился с одной клетки на другую любым из двух возможных способом). Тот же вопрос для короля и ладьи. Как изменится ответ для шахматной доски размером 7*7? Изложите ответ в терминах теории графов.

3. Может ли ходом шахматный конь побывать на каждой клетке шахматной доски размером 8*8 ровно один раз и возвратиться в начальную клетку. Тот же вопрос для короля и ладьи. Как изменится ответ для шахматной доски размером 7*7? Изложите ответ в терминах теории графов.

4. Приведите пример графа, который является эйлеровым, но не гамильтоновым.

5. Приведите пример графа, который является гамильтоновым, но не. эйлеровым

6. Что можно сказать о графах, являющихся одновременно эйлеровыми и гамильтоновыми?

Плоские и планарные графы

 

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

 

Таким образом, возникает понятие плоского графа.

 

Определение:Плоским графом называется граф, вершины которого являются точками плоскости, а ребра – непрерывными линиями без самопересечений, соединяющими соответствующие вершины так, что никакие два ребра не имеют общих точек, кроме инцидентной им обоим вершины.

 

                    а                                                  б

Рис. 1. Плоские графы.

 

Определение:
  Любой граф, изоморфный плоскому графу, будем называть планарным.

                                        Рис.2.

 

Граф на рис.2 является планарным, так как он изоморфен графу на рис 1.б.

 

Очевидны следующие утверждения:

1) всякий подграф планарного графа планарен;

2) граф планарен тогда и только тогда, когда каждая его связная компонента – планарный граф.

О планарных графах говорят, что они укладываются на плоскости (имеют плоскую укладку).