Найти все бесхордовые циклы в неориентированном графе

Как найти все бесхордовых циклов в неориентированном графе?

Например, для графика

0 --- 1
|     | \
|     |  \
4 --- 3 - 2

алгоритм должен возвращать 1-2-3 и 0-1- 3-4, но никогда не 0-1-2-3-4.


(Примечание: [1] Этот вопрос не то же самое, что поиск малых циклов в плоском графе , потому что граф не является обязательно планарно. [2] Я читал статью Генерация всех циклов, циклов без хорд и гамильтоновых циклов с принципом исключения , но я не понимаю, что они делают :) [3] I попробовали CYPATH , но программа выдает только счетчик, алгоритм EnumChordlessPath в readme.txt содержит существенные опечатки, а код C - беспорядок. [4] Я не пытаюсь найти произвольный набор фундаментальных циклов . Основа цикла может иметь хорды.)

28
задан Community 23 May 2017 в 12:02
поделиться