Каково общее число гамильтоновых цепей в полном неориентированном графе, когда одно или несколько ребер всегда должны быть включены?

Question

Для полного неориентированного графа G, где вершины проиндексированы как [n] = {1,2,3,...,n} where n >= 4.Я знаю, что общее число гамильтоновых цепей в G составляет (n-1)! / 2

1. Если мы должны пересечь границу {1,2}, сколько там гамильтоновых цепей?
2. Как насчетесли необходимо пройти несколько последовательных ребер, например, {1,2} {2,3}?
3. Что если необходимо пройти несколько непоследовательных ребер, например, {1,2} {3,4}?

Интуитивно, для части 1,Кажется, ответ (n-2)! /2, но я не совсем уверен.Что касается других частей, я полностью озадачен.

Любая помощь очень ценится!

Answer 1

1) Подмножество 2

2) Рассмотрим G' = G - {v1, v2, v3...vk} (вершины в порядке появления в последовательных ребрах E нужно использовать).Для каждой гамильтоновой цепи C в G 'вы можете добавить последовательность ребер в любую часть C, в результате чего получите C[0..i] + {C[i], v1} + E + {vk, C[i]} + C[i..n].

Для графа G ', there are (n - 1 - k)! / 2 Гамильтоновы цепи.Для каждой из этих цепей вы можете расширить ее между любыми 2 парами последовательных ребер, как мы обсуждали выше.Это, | C |способы сделать это.Таким образом, ответ будет (n - 1 - k)! / 2 * |C| = (n - 1 - k)! / 2 * (n - k).

Вам все еще нужно доказать, что мы подсчитываем все их таким образом и что мы не учитываем дубликаты.

3) Обобщение 2. Вы подсчитываете гамильтоновы цепи без каких-либовершина, упомянутая в E, а затем начните добавлять 1 на 1 ребра, которые необходимо пройти.