Поперечный граф с использованием гамильтоновых циклов
Допустим, нам дан график, и мы хотим найти минимальное количество циклов Гамильтона, необходимое для прохождения каждого узла графа.
Если граф имеет 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.