绘制一个具有 1800 条哈密顿路径的 7 顶点简单图

Question

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

Answer 1

那个属性好像没有7顶点图。至少我没找到:-)

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

在几乎完整的图中删除一条边会删除很多路径。因此，要生成恰好 1800 条路径，最多可以删除 3 条边。这是一个 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 条路径更重要。

绘制一个具有 1800 条哈密顿路径的 7 顶点简单图

Draw a 7 vertex simple graph with exactly 1800 hamiltonian paths

graph-theory

hamiltonian-cycle