繪製一個具有1800個哈密爾頓路徑的7頂點簡單圖形

Question

我在準備「圖論導論」課程的考試時遇到了這個問題。如果有人提供方法來處理這樣一個問題（如果您指定了頂點數和哈密頓或歐幾里得路徑並詢問圖的結構），我將不勝感激。

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(''): 
     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點的路徑。