나는그래프에서 해밀턴 경로 수를 찾는 방법은 무엇입니까?
링크 우리가 사용할 수있는 내가 알아 낸
https://code.google.com/codejam/contest/32004/dashboard#s=p2
질문에 우리는 완전한 그래프에서 K 가장자리를 제거하면 해밀턴 경로의 수를 알아 말합니다이 구글 Codejam 문제를 노력하고 있어요 포함 제외 원칙은 숫자를 찾으려면
하지만 내 문제는 경로의 수를 결정하는 방법입니다. 일부 'x'개의 수의 가장자리가 전체 그래프에서 제거되었습니다 (제거 된 가장자리가 있음)
아이디어는 경로를 계산하는 대신 순열을 계산하는 것입니다. 이렇게하면 각 경로가 2 * n 번 고려됩니다.
순열이 n 인 경우 총 수!
나쁜 사이클을 계산할 때 충격 완화 원칙을 사용합시다. 한쪽 가장자리가 금지되면 2 * n * (n-2)! 이 모서리를 포함하는 경로 (두 개의 인접한 정점을 함께 배치하고 나머지는 어디든 간다).
금지 된 가장자리가 여러 개있는 경우 모든 vetrices는 여러 개의 독립적 인 그룹 (이 가장자리로 연결된 체인을 형성 함)으로 나뉩니다. 각 그룹을 배치하는 방법에는 두 가지가 있습니다 (되돌릴 수 있음). 모든 그룹은 서로 임의로 치환 될 수 있습니다. 요소의 나머지는 아무 곳에 나 배치 할 수 있습니다 (이항 계수가 어떤 계승을 곱하는 데 기여합니다). 또 하나의 경고가 있습니다. 체인이 감쌀 수 있습니다. 하지만 체인이 하나만있을 수 있습니다. 따라서 위에서 설명한 알고리즘을 사용하여 나머지를 배치하는 방법의 수를 감싸고 계산하는 체인을 반복 할 수 있습니다.
한 쪽 가장자리가 금지되면 두 꼭지점을 단일 꼭지점으로 연결한다고 생각합니까? 체인 랩이 무엇인지 설명해 주시겠습니까? – Ezio
@Ezio 네, 연결된 두 개의 vetrices는 하나의 꼭지점으로 처리됩니다. 주위를 감싸는 것은 가장자리 (1,2)가 금지되어 있고, 1이 순열의 첫 번째 요소이고 2가 마지막 것임을 의미합니다. – kraskevich
n 개의 꼭지점의 전체 그래프에서 두 개의 엣지가 제거되었다고 가정하면 포함 수식을 수학적으로 어떻게 표현할 수 있습니까? – Ezio