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

Question

在“图论概论”课程准备考试时，我遇到了这个问题。如果有人给出方法来处理这样的问题，我会非常感激的(在这里，您指定顶点数、Hamiltonian路径或欧几里德路径，并询问图的结构)。

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个路径。