работа по курсу «Дискретная математика» Тема: Разработка алгоритма и программного обеспечения для решения прикладной задачи теории графов (стр. 4 из 11)

Приведем некоторые наиболее простые методы выделения гамильтоновых цепей и циклов в графе G =(V,X), где V = {v₁ ,v₂ ,…,v_n}. Самым простым является метод перебора всевозможных перестановок v_i1 ,v_i2 ,…,v_in множества V. Для каждой из них проверяем, является ли v_i1v_i2…v_in маршрутом в G. Если является, то v_i1v_i2 …v_in - гамильтонова цепь в G, в противном случае переходим к другой перестановке. Тогда по окончании перебора будут выделены все гамильтоновы цепи в графе G. Аналогично для выделения гамильтоновых циклов перебираем всевозможные перестановки v₁v_i1v_i2 …v_in-1 множества V, для каждой из которых проверяем, является ли v₁v_i1v_i2…v_in-1v₁ маршрутом в G. Если является, то v₁v_i1v_i2…v_in-1v₁ – гамильтонов цикл в G, в противном случае переходим к следующей перестановке. Тогда по окончании перебора будут выделены все гамильтоновы циклы в графе G. Очевидно, что при выделении гамильтоновых цепей придется перебрать n! перестановок, а при выделении всех гамильтоновых циклов - (n-1)! перестановок. При этом в случае полного графа ни одна из перестановок не окажется отброшенной, т.е. данный метод является эффективным для графов, близких к полным.

Отметим, что описанный метод не учитывает информации об исследуемом графе G и является как бы ориентированным на самый “худший” случай, когда G – полный граф.

Для того, чтобы сократить число шагов в предложенном методе, рассмотрим следующий алгоритм. Предположим, что решение имеет вид последовательности <v₁, ... v_n>. Идея метода состоит в следующем: решение строится последовательно, начиная с пустой последовательности (длины 0). Далее, имея частичное решение <v₁, ... v_i>, ищем такое допустимое значение v_i+1, которое еще не было использовано, добавляем его к пройденному частичному решению и продолжаем процесс для нового частичного решения <v₁, ... v_i+1>. В противном случае, если такого значения v_i+1 не существует, возвращаемся к предыдущему частичному решению <v₁, ... v_i-1> и продолжаем процесс, пытаясь определить новое, еще не использованное допустимое значение v_k. Такие алгоритмы носят название “алгоритмы с возвратом” (англ.: backtracking).

2 1

1 5 3 12 14

4

123 125 143 145

1234 1235 1253 1254 1432 1435 1452 1453

14321 14352

12341 12354 12534

14325 14521 14532

12345 12541 12543 14523

123541 125341 143521 145321

Рис. 2

Процесс поиска с возвращением удобно проиллюстрировать в терминах обхода в глубину в некотором дереве поиска, которое строится следующим образом. Каждая вершина дерева соответствует некоторому частичному решению <v₁,...v_i>, причем вершины, соответствующие последовательностям вида <v₁,.. v_i, y>, и являются преемниками вершины <v₁,... v_i>. Корнем данного дерева является пустая последовательность. В случае построения гамильтонова цикла в качестве корня может выступать любая вершина.

При обходе дерева в глубину вершины дерева посещаются в таком порядке: сначала посещаем корень дерева v₁, а затем (если v₁ – не висячая вершина) для каждого преемника v_i корня v₁ рекурсивно обращаемся к процедуре обхода в глубину для того, чтобы обойти все поддеревья с корнями v_i в порядке, в котором упорядочены вершины v_i как преемники корня v₁.