Эйлеровы и гамильтоновы циклы в графе. Алгоритм Флери построения эйлеровых циклов в графе. Алгоритм Робертеса и Флореса по строения гамильтоновых циклов в графе

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

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

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

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

1. Строится матрица М, число строк которой равно максимальной степени вершин графа, а число столбцов — количеству вершин графа. Каждый элемент mij- это i-я вершина графа, смежная с вершиной Xj. Вершины при построении матрицы упорядочиваются.

2. Присвоить p=xi, где xi —начальная вершина графа. Через р обозначена последняя вершина, включенная в гамипьтонов цикл. S{x}, где S —множество вершин, включенных в гамильтонов цикл.

3. Если в столбце матрицы М соответствующем вершине р есть возможная вершина, т.е. вершина еще не принадлежащая S, то переход к шагу4, иначе —7.

4.В столбце, соответствующем вершине р выбирается первая возможная вершина хк. Эта вершина присоединяется к множеству S и

p=Xк.

5. Если мощность множества |М|=n, где n — число вершин графа, то найдена гамипьтонов а цепь. Переход к шагу 6, иначе — 3.

6. Если существует дуга (ребро) (р, X1.)), то найден гамильтонов цикл. Если надо найти все гамильтоновы циклы, переход к 7, иначе - работа алгоритма завершена.

7. Возвращение. Их множеств a S удаляется последняя включенная вершина х_г, если при этом S=0, то работа алгоритма завершена, иначе—p=x_r-i.

8. Если в столбце р существуют вершины, следующие за х_r то переход к 4, иначе- х_г= x_r.i и переход к 7.