정확한 1800 개의 해밀턴 경로를 가진 7 개의 꼭지점 단순 그래프 그리기

Question

'Graph Theory 소개'에서 강의를 준비하면서이 질문을 보았습니다. 나는 누군가가 그러한 질문 (당신이 정점의 수와 해밀턴 또는 유클리드 경로를 지정하고 그래프의 구조를 묻는 곳)에 접근하는 방법론을 제공하면 크게 감사 할 것입니다.

Answer 1

그 속성을 가진 꼭지점 그래프가 7 개없는 것 같습니다. 적어도 찾지 못했습니다 :-)

완전한 7 정점 그래프 (K_7)에는 7 개가 있습니다! 경로 (순열 수와 동일 : 5040). K_7에서 한 모서리를 제거하면 5 * 6이 생성됩니다! 경로 (3600).

거의 완전한 그래프에서 하나의 가장자리를 제거하면 많은 경로가 제거됩니다. 그 때문에 정확히 3 개의 가장자리에서 1800 개의 경로를 정확하게 생성 할 수 있습니다. 다음은 1, 2 및 3 개의 가장자리가없는 경로 수를 확인하는 파이썬 스크립트입니다.

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 

출력은 다음과 같습니다이 경로의 방향을 제외하고, 정확히 1800 경로에는 그래프입니다 K_7보다 중요하지 않습니다 뺀 에지 1800 개 경로가

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') 

.