Как я могу найти количество гамильтоновых циклов в полном неориентированном графе?
Вас показали PadLeft и PadRight. Это заполнит пропавших без вести PadCenter.
public static class StringUtils
{
public static string PadCenter(this string s, int width, char c)
{
if (s == null || width <= s.Length) return s;
int padding = width - s.Length;
return s.PadLeft(s.Length + padding / 2, c).PadRight(width, c);
}
}
Примечание к сам: не забывайте обновлять собственный CV: "Однажды, я даже зафиксировал код Joel Coehoorn!";-D - Саржа
1 ответ
Поскольку граф завершен, любая перестановка, начинающаяся с фиксированной вершины, дает (почти) уникальный цикл (последняя вершина в перестановка будет иметь ребро, возвращающееся к первой фиксированной вершине.За исключением одного: если вы посещаете вершины в цикле в обратном порядке, то это действительно тот же цикл (из-за этого число составляет половину того, что перестановки ( n-1) вершины дадут вам).
например, для вершин 1,2,3, зафиксируйте «1», и вы получите:
123 132
, но 123 обратное (321) - это поворот (132), потому что 32 - это обратное 23.
Есть (n-1)! перестановки нефиксированных вершин, половина из которых является обратной по отношению к другой, так что в полном графе из n вершин имеется (n-1)! / 2 различных гамильтоновых циклов.