Учебное пособие C#. Алгоритмы и структуры данных н. А. Тюкачев, В. Г. Хлебостроев издание третье, стереотипное 1 / 23
Download 1.85 Mb. Pdf ko'rish
|
C# Алгоритмы и структуры данных 2018 Тюкачев, Хлебостроев
- Bu sahifa navigatsiya:
- Теорема Поша
|
5.5.2. Г
АМИЛЬТОНОВ ЦИКЛ . А ЛГОРИТМЫ С ВОЗВРАТОМ Напомним, что гамильтоновой цепью графа называется маршрут, кото- рый проходит через каждую вершину графа ровно один раз. Если такой мар- шрут замкнут, то он называется гамильтоновым циклом, а соответствующий граф – гамильтоновым графом. Такие названия цепей и циклов связаны с именем ирландского математика и физика-теоретика Уильяма Роуэна Га- мильтона (Hamilton W.), который в 1859 г. предложил следующую игру- головоломку: требуется, переходя по очереди от одной вершины додекаэдра к другой вершине по его ребру, обойти все 20 вершин по одному разу и вер- нуться в начальную вершину. Достаточные условия существования гамильтонова цикла были сформу- лированы в работах Оре (Ore O.) и Дирака (Dirac G. A.) в 1950-х годах. Но в наиболее общем виде они представлены в теореме, доказанной венгерским 18 / 23 180 математиком Лье Поша (Posa L.) в 1962 году. Отметим, что условие Поша су- ществования гамильтонова цикла является достаточным, но не необходимым. Теорема Поша Пусть граф G имеет p > 2 вершин. Если для всякого n, 0 < n < (p − 1) / 2, количество вершин со степенями, не превосходящими n, меньше n и для не- четного p количество вершин степени (p − 1) / 2 не превосходит (p − 1) / 2, то G — гамильтонов граф. Следствие В полном графе G(V, E) всегда существует гамильтонов путь. К сожалению, пока еще неизвестны эффективные методы решения по- ставленной задачи. Поэтому воспользуемся методом перебора с возвратом. 1. Начиная с определенной вершины (пускай это будет вершина с номером 1), будем продвигаться вперед по графу, включая очередное ребро в гамильтонов цикл. 2. При найденных первых k компонентах решения рассматрива- ем ребра, которые выходят из последней вершины. Если на- ходим ребро, которое ведет в непосещенную ранее вершину, добавляем новую вершину в цикл — она становятся про- смотренной. При этом (k + 1)-ая компонента решения полу- чена. 3. При отсутствии такой вершины возвращаемся к предыдущей и ищем другие смежные с ней. Цикл считается найденным, если просмотрены все вершины графа, и из последней вершины можно попасть в начальную. Такой цикл можно вывести на экран и продолжить поиск других циклов. Рекурсивная реализация этого алгоритма представлена в листинге 5.36. Download 1.85 Mb. Do'stlaringiz bilan baham: 
|