최소 모서리 수를 추가하여 그래프에서 min-cut 크기를 늘리는 방법

Question

문제 : T = (V, E) 인 경우. 하나의 가장자리가 새로 생성 된 그래프에서 제거 된 경우에도 여전히 모든 꼭지점에서 다른 꼭지점까지의 경로가 있도록 최소 모서리 수를 추가합니다.

나는이 문제가 현재 min-cut 1에서 그래프의 min-cut 크기를 2로 증가시키는 것으로 줄일 수 있다고 믿는다. 그러나 그렇게하는 효율적인 알고리즘은 무엇일까?

Answer 1

여기 알고리즘입니다. 어떤 방향없는 그래프에서도이 문제를 해결합니다. 몇 가지 단순화 후에 트리에 적용될 수 있습니다 (1 단계는 필요 없음).

1. 그래프의 모든 브리지를 DFS 또는 Bridge-finding algorithm by Robert Tarjan과 함께 찾습니다.
2. 각 브리지없는 서브 그래프가 단일 정점으로 대체되는 그래프를 만듭니다 (실제로는 트리입니다).
3. 트리의 모든 체인을 단일 가장자리로 접습니다.
4. 두 리프 사이의 경로를 찾으십시오 (길이가 적어도 3 일 경우 가능).
5. 이 경로의 양쪽 끝에 해당하는 원본 그래프의 부 그래프에서 두 개의 꼭지점을 선택하고 연결합니다.
6. 이 경로를 단일 꼭지점으로 접습니다.
7. 트리에 하나 개 이상의 정점이 있지만, 3 단계

우리는 최적의 열쇠입니다 6 단계 후 새로운 불필요한 잎을 얻을 수 있습니다 4 단계 보장에서 반복합니다.

Answer 2

Evgeny의 솔루션은 매우 훌륭하지만 여기서는 나무에서 작동하며 그 정확성을 쉽게 볼 수있는 간단한 솔루션이 있습니다.

L을 트리의 (원래) 잎이라고합시다. T. n을 n을 제거하여 얻은 각 하위 트리가 원래 나뭇잎 인 |L|/2 개가되도록 트리의 노드로 보자. 항상 그런 노드를 찾으려면 n입니다.

₁T, T 2, ..., K T는 n 제거하여 얻어진 서브 트리하자. 모든 원래 리프 (L)는 T _i 중 하나에 있습니다. 임의의 쌍의 두 원본 나뭇잎이 고유 한 하위 트리에 속하는 제약 조건을 사용하여 원본 나뭇잎과 최대 비 연속 쌍을 구성합니다. (이것은 부분이 서브 트리에있는 원래 나뭇잎 인 전체 k-partite 그래프에서 최대 일치를 생성하는 것과 개념적으로 동일합니다.)

|L|이 짝수이면 모든 원래 리프가 일부 쌍에 존재하고 각 쌍에 해당하는 가장자리를 추가하면 결과 그래프가 2 연결됩니다. 이 경우에는 |L|/2 가장자리를 추가해야합니다.

|L|이 홀수 인 경우 원본 리프 하나가 페어링되지 않으므로이 리프를 다른 하위 트리에있는 임의의 원래 리프에 연결할 수 있습니다. 이 경우 (|L|+1)/2 가장자리를 추가해야합니다.