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

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

Если граф имеет 6 узлов и у нас есть ребра:

1-2
2-3
3-1
3-4
4-5
5-6
6-4

Очевидно, минимальное количество гамильтоновых циклов составляет 2 (1-2-3 и 4-5-6).

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

Число узлов в графе равно N(N<=50), а число ребер может доходить до n(n-1)/2.

0 ответов

Другие вопросы по тегам