graph-theory - 画一个 7 个顶点的简单图，正好有 1800 条哈密顿路径

Question

我在准备“图论导论”课程的考试时遇到了这个问题。如果有人提供解决此类问题的方法（您指定顶点数和哈密顿或欧几里得路径并询问图形的结构），我将不胜感激。

Answer 1

似乎没有具有该属性的 7 个顶点图。至少我没有找到它:-)

在完整的 7 个顶点图 (K_7) 中有 7 个！路径（与排列​​数相同：5040。）从 K_7 中移除一条边会产生 5*6！路径（3600）。

在几乎完整的图中删除一条边会删除很多路径。因此，最多可以删除 3 个边缘，从而产生 1800 条路径。这是一个 python 脚本，它检查没有一条、两条和三条边的路径数。

without_edges = (
    # One edge
    ('01',),
    # Two edges
    ('01', '23'),
    ('01', '12'),
    # Three edges
    ('01', '23', '45'),
    ('01', '02', '34'),
    ('01', '02', '23'),
    ('01', '02', '03'),
    # Four edges, few for testing
    ('01', '23', '45', '06'),
    ('01', '23', '45', '02'),
    ('01', '02', '34', '56'),
    ('01', '02', '34', '45'),
    ('01', '02', '34', '05'),
    # ...
)

for w_edges in without_edges:
    w_e = w_edges + tuple(e[::-1] for e in w_edges)
    n = 0
    for p in permutations('0123456'):
        p = ''.join(p)  # Represent permutation as a string
        if all(e not in p for e in w_e):
            n += 1
    print n, w_edges

输出是：

3600 ('01',)
2640 ('01', '23')
2400 ('01', '12')
1968 ('01', '23', '45')
1824 ('01', '02', '34')
1632 ('01', '02', '23')
1440 ('01', '02', '03')
1392 ('01', '23', '45', '06')
1272 ('01', '23', '45', '02')
1392 ('01', '02', '34', '56')
1320 ('01', '02', '34', '45')
1152 ('01', '02', '34', '05')

没有图正好有 1800 条路径，除了路径的方向比 K_7 减去一条边有 1800 条路径并不重要。