정확성 증명:그래프 이론의 나무 직경에 대한 알고리즘

StackOverflow https://stackoverflow.com//questions/20010472

문제

나무의 직경을 찾기 위해 트리에서 임의의 노드를 가져와서 BFS를 수행하여 가장 멀리 있는 노드를 찾은 다음 해당 노드에서 BFS를 수행합니다.두 번째 BFS로부터 가장 먼 거리가 직경을 산출합니다.

그런데 이것을 어떻게 증명해야 할지 잘 모르겠습니다.노드 수에 맞춰 인덕션을 사용해 보았는데 경우가 너무 많습니다.

어떤 아이디어라도 대단히 감사하겠습니다 ...

도움이 되었습니까?

해결책

첫 번째 BFS X에서 발견 한 엔드 포인트를 호출 해 봅시다. 중요한 단계는이 첫 번째 단계에서 발견 된 X가 항상 "작동"이라는 것을 증명합니다. 즉, 항상 가장 긴 경로의 한쪽 끝에있는 것입니다. 일반적으로 가장 긴 경로가 하나 이상있을 수 있습니다. 가장 긴 경로.

힌트 : 2 개의 정점 U와 V 사이의 경로가 더 긴 경로가 있다고 가정합니다.

U와 V 사이의 고유 한 경로에서 가장 높음 (루트에 가장 가깝게) 정점 h가 있어야합니다. H는 두 가지 가능성이 있습니다. H는 BFS의 루트에서 X 로의 경로에 있거나 그렇지 않습니다. 두 경우 모두 두 경우 모두 일부 경로 세그먼트를 X 로의 경로로 대체하여 U-V 경로를 적어도 만들 수 있습니다.

[편집] 실제로는 결국 2 건을 별도로 대우 할 필요가 없습니다. 그러나 나는 종종 구성을 여러 번 (또는 심지어 많은 경우)으로 구성하고 각각을 별도로 치료하는 것이 더 쉽습니다. 여기서, H가 BFS 루트로부터 X 로의 경로에있는 경우는 쉽게 다루고 다른 경우에 단서를 제공합니다.

[편집 2] 나중에 다시 오신 것을 고려해야 할 두 가지 경우는 (i) UV 경로가 루트에서 X 로의 경로를 교차합니다 ( 일부 정점 y, 꼭 자외선 경로의 가장 높은 지점 H에서 반드시 사용되지 않음; (ii) 그렇지 않습니다. 우리는 여전히 각각의 경우를 증명하기 위해 H를 필요로합니다.

다른 팁

나는 운동하러 갈거야 j_random_hacker의 힌트.허락하다 s, t 최대한 멀리 떨어져 있는 쌍이 되어야 합니다.허락하다 u 임의의 정점이 됩니다.우리는 다음과 같은 회로도를 가지고 있습니다.

    u
    |
    |
    |
    x
   / \
  /   \
 /     \
s       t ,

어디 x 의 교차점이다 s, t, u (즉.정점 사이의 세 경로 각각에 있는 고유한 정점입니다.

한다고 가정 v 는 정점에서 최대로 떨어져 있는 정점이다. u.이제 회로도가 다음과 같다면

    u
    |
    |
    |
    x   v
   / \ /
  /   *
 /     \
s       t ,

그 다음에

d(s, t) = d(s, x) + d(x, t) <= d(s, x) + d(x, v) = d(s, v),

불평등이 유지되는 이유는 다음과 같습니다. d(u, t) = d(u, x) + d(x, t) 그리고 d(u, v) = d(u, x) + d(x, v).대칭적인 경우가 있습니다. v 사이에 붙는다 s 그리고 x 대신에 x 그리고 t.

다른 경우는 다음과 같습니다

    u
    |
    *---v
    |
    x
   / \
  /   \
 /     \
s       t .

지금,

d(u, s) <= d(u, v) <= d(u, x) + d(x, v)
d(u, t) <= d(u, v) <= d(u, x) + d(x, v)

d(s, t)  = d(s, x) + d(x, t)
         = d(u, s) + d(u, t) - 2 d(u, x)
        <= 2 d(x, v)

2 d(s, t) <= d(s, t) + 2 d(x, v)
           = d(s, x) + d(x, v) + d(v, x) + d(x, t)
           = d(v, s) + d(v, t),

그래서 max(d(v, s), d(v, t)) >= d(s, t) 평균적인 주장에 의해, 그리고 v 최대로 먼 쌍에 속합니다.

여기를 보는 다른 방법이 있습니다 :

g = ( V , e < 강력한>)는 정점 세트 v e

다음 알고리즘을 고려하십시오.

  1. count = 0으로 e 에있는 모든 가장자리를 초기에 처음으로 제거하게하십시오. c 을 초기에 v 과 동일하게하십시오.
  2. 는 정확히 하나의 무색 가장자리가있는 모든 정점을 포함하는 v 의 서브 세트 '을 고려한다.
    • v '이 비어 있으면 d = count * 2를 멈추고 정지시킨다. v '을 포함하는 경우 정확히 두 개의 요소가 포함 된이어서 상호 (무색) 가장자리 녹색을 착색하고 d = count * 2 + 1, 그리고 정지.
    • 달리, v '은 적어도 3 개의 정점을 포함한다. 다음과 같이 진행하십시오 :
  3. 증분 count
  4. 무결점이없는 c 에서 모든 정점을 제거하십시오.
  5. v 의 각 꼭지점에 대해 각각의 녹색 가장자리가 빨간색으로 색을 색칠하십시오 (일부 정점은 그러한 가장자리가 0이 될 수 있음).
  6. v '의 각 꼭지점에 대한 '
  7. 단계 (2)로 돌아갑니다.

    8. 기본적으로 나뭇잎에서 나뭇잎에서 그래프를 색상으로 녹색으로 잎에 최대 거리로 마킹하고 짧은 거리 만 짧은 거리 만 표시합니다. 한편, C 의 노드는 잎과의 최대 거리가 더 짧은 까지 멀어 질 때까지 멀어 질 것이다. 잎과 가장 큰 최대 거리가있는 하나 또는 두 개의 노드 만 포함합니다.

    건설, 잎 정점에서 가장 가까운 센터 정점으로의 모든 간단한 경로는 녹색 가장자리만을 가로 지르는 가장 가까운 센터 정점으로 ( count ) 잎 정점에서 가장 가까운 센터로의 모든 간단한 경로입니다. 정점 (적어도 하나의 적색 가장자리를 이송)이 짧습니다. 또한

    를 발견 할 수 있습니다.

    • 이 알고리즘은 항상 g 의 모든 가장자리를 적색 또는 녹색으로 착색하고 c 을 남겨두고 종결됩니다. 하나 또는 두 개의 요소가 있습니다.
    • 알고리즘 종단에서, d 은 가장자리에서 측정 된 g 의 직경이다.
    • v 의 g 의 최대 길이 간단한 경로가 주어진다. / strong> v 에서 시작하는 것은 정확히 모든 정점을 포함하고 잎을 종결시키고 중앙과 멀리있는 엔드 포인트 사이의 녹색 가장자리 만 트래버스합니다. 이들은 센터에서 가장 먼 나뭇잎 중 하나에 센터를 가로 질러 V 에서 이동합니다.

    이제 위의 비가 내리는 알고리즘이 더 실용적 일 수 있습니다. V 임의의 정점에서 정확히 하나의 단순 경로 가운데 정점에서 끝나고 모든 정점을 포함하는 간단한 경로 이 정확히 있습니다. 센터 ( g 가 트리이므로 c 에 두 개의 정점이있는 경우 가장자리를 공유합니다) ...에 v> g 의 최대 간단한 경로는 모두 < > P 중심에서 리프에서 리프까지의 간단한 경로로 녹색 가장자리 만 횡단합니다.

    우리의 목적을위한 핵심 포인트는 다른 끝점의 수신자가 반드시 녹색이기도합니다. 따라서 가장 긴 경로를 검색 할 때 가장 긴 경로를 검색 할 때 우리는 중심의 잎에서 다른 잎으로의 잎에서 녹색 가장자리를 횡단하는 것에 액세스 할 수 있습니다. 그것들은 g 의 최대 길이의 간단한 경로이므로 두 번째 검색이 실제로 그래프 직경을 밝힐 것이라고 확신 할 수 있습니다.

1:procedureTreeDiameter(T)

2:pick an arbitrary vertex v where v∈V

3:u = BFS ( T, v )

4:t = BFS ( T, u )

5:return distance ( u, t )

Result: Complexity = O(|V|)

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top