간단한 경로의 평균 길이를 계산하는 알고리즘

Question

연결된 그래프와 두 개의 노드 S와 T가 주어지면 S에서 T까지 다양한 간단한 경로 (주기없는)가 많을 수 있습니다.이 경로의 평균 길이를 찾는 효율적인 알고리즘이 있습니까?

Answer 1

두 노드 사이의 간단한 경로 수를 계산하는 다항식 알고리즘이 P= NP를 의미합니다.이 결과는 용감한 (열거 및 신뢰성 문제, 1979)의 복잡성 때문입니다.

이제 $ \ text {avg} (g, u, v) $ 을 다항식 시간에 계산할 수있는 모순을 발견 할 것으로 상상해보십시오.

$ g + l $ 길이의 간단한 경로를 추가로 인한 그래프가되어 $ l $ $ u $ 및 $ v $ $ g $ . 이 새로운 경로는 $ l-1 $ 새 노드로 만들어졌으며 $ u $의 이전 경로를 방해하지 않습니다. $ v $ , $ l \ geq 2 $ .

다음 $ \ text {avg} (g + 3, u, v) - \ text {avg} (g + 2, u, v) $ = $ 1 / (\ # \ text {paths} (g, u, v) +1) $ , $ \ # \ text {paths} (g, u, v) $ polynomial 시간에 $ . 그러나 우리는 이것이 다항식 시간, 모순에서 수행 될 것으로 예상 될 수 없다는 것을 압니다.