Записи с меткой ‘графы’

Получение списка фундаментальных циклов графа

Дата: 10th Ноябрь 2010. Автор: Maxsbelt. Рубрика: C#, Алгоритмы, Графы
Метки: , ,
3

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

Определяем, связан ли граф (Если нет — циклов нет);
Строим матрицу смежности остовного дерева графа;
Устраиваем цикл по хордам;
Выводим список фундаментальных циклов графа.
Приступим к реализации алгоритма

Цикл гамильтона

Дата: 6th Июнь 2010. Автор: KAS. Рубрика: Алгоритмы
Метки: , ,
0

Циклом Гамильтона называется путь проходящий через каждую вершину графа только 1 раз. Псевдокод: procedure ГАМИЛЬТ(k) {генерация всех гамильтоновых циклов, являющихся расширением последовательности X[1], . . ., X[k – 1]: массив X — глобальный } begin for y принадлежит ЗАПИСЬ [X[k – 1]] do if (k = n +1) and (y = v0) then write(X[1], . [...]