간선 연결도 / 정점 연결도¶
정의¶
$n$개의 정점과 $m$개의 간선을 가진 무방향 그래프 $G$가 주어졌다고 합시다. 간선 연결도와 정점 연결도는 모두 그래프를 설명하는 특성입니다.
간선 연결도¶
그래프 $G$의 간선 연결도 $\lambda$는 그래프 $G$가 연결되지 않도록 만들기 위해 삭제해야 하는 간선의 최소 개수입니다.
예를 들어 이미 연결되지 않은 그래프의 간선 연결도는 $0$이고, 브리지가 하나 이상 있는 연결 그래프의 간선 연결도는 $1$이며, 브리지가 없는 연결 그래프의 간선 연결도는 $2$ 이상입니다.
그래프 $G$에서 간선 집합 $S$의 모든 간선을 제거한 후 정점 $s$와 $t$가 서로 다른 연결 요소에 속하게 되면, 집합 $S$가 정점 $s$와 $t$를 분리한다고 합니다.
그래프의 간선 연결도가 가능한 모든 쌍 $(s, t)$에 대해 두 정점 $s$와 $t$를 분리하는 그러한 집합의 최소 크기와 같다는 것은 자명합니다.
정점 연결도¶
그래프 $G$의 정점 연결도 $\kappa$는 그래프 $G$가 연결되지 않도록 만들기 위해 삭제해야 하는 정점의 최소 개수입니다.
예를 들어 이미 연결되지 않은 그래프의 정점 연결도는 $0$이고, 단절점이 있는 연결 그래프의 정점 연결도는 $1$입니다. 완전 그래프의 정점 연결도는 $n-1$로 정의합니다. 그 밖의 모든 그래프에서는 간선으로 연결되지 않은 정점 쌍을 찾아 나머지 $n-2$개의 정점을 모두 제거할 수 있으므로, 정점 연결도가 $n-2$를 넘지 않습니다.
그래프 $G$에서 정점 집합 $T$의 모든 정점을 제거한 후 두 정점이 서로 다른 연결 요소에 속하게 되면, 집합 $T$가 정점 $s$와 $t$를 분리한다고 합니다.
그래프의 정점 연결도가 가능한 모든 쌍 $(s, t)$에 대해 두 정점 $s$와 $t$를 분리하는 그러한 집합의 최소 크기와 같다는 것은 자명합니다.
성질¶
Whitney 부등식¶
Whitney 부등식(1932)은 간선 연결도 $\lambda$, 정점 연결도 $\kappa$, 그리고 그래프에 있는 정점의 최소 차수 $\delta$ 사이의 관계를 나타냅니다:
직관적으로, 그래프를 연결되지 않게 만드는 크기 $\lambda$의 간선 집합이 있다면, 각 간선의 끝점 중 하나씩을 골라 역시 그래프를 연결되지 않게 만드는 정점 집합을 만들 수 있습니다. 그리고 이 집합의 크기는 $\le \lambda$입니다.
또한 최소 차수 $\delta$를 가진 정점을 골라 그 정점에 연결된 모든 간선을 제거하면, 역시 연결되지 않은 그래프를 얻게 됩니다. 따라서 두 번째 부등식 $\lambda \le \delta$가 성립합니다.
흥미롭게도 Whitney 부등식은 더 개선할 수 없습니다. 즉, 이 부등식을 만족하는 임의의 세 수에 대해 그에 대응하는 그래프가 적어도 하나 존재합니다. 그러한 그래프 중 하나는 다음과 같이 구성할 수 있습니다: 그래프는 $2(\delta + 1)$개의 정점으로 이루어지며, 처음 $\delta + 1$개의 정점은 클리크(모든 정점 쌍이 간선으로 연결됨)를 이루고, 나머지 $\delta + 1$개의 정점은 두 번째 클리크를 이룹니다. 추가로 두 클리크를 $\lambda$개의 간선으로 연결하되, 첫 번째 클리크에서는 서로 다른 정점 $\lambda$개를 사용하고 두 번째 클리크에서는 정점 $\kappa$개만 사용하도록 합니다. 이렇게 만든 그래프는 세 가지 특성을 모두 갖게 됩니다.
Ford-Fulkerson 정리¶
Ford-Fulkerson 정리에 따르면, 두 정점을 연결하는 간선이 서로 겹치지 않는 경로의 최대 개수는 이 두 정점을 분리하는 간선의 최소 개수와 같습니다.
값 계산하기¶
최대 흐름을 이용한 간선 연결도¶
이 방법은 Ford-Fulkerson 정리에 기반합니다.
모든 정점 쌍 $(s, t)$에 대해 반복하면서, 각 쌍 사이에 존재하는 서로소인 경로의 최대 개수를 구합니다. 이 값은 최대 흐름 알고리즘을 사용하여 구할 수 있습니다: $s$를 소스로, $t$를 싱크로 사용하고, 각 간선에 용량 $1$을 부여합니다. 그러면 최대 흐름이 서로소인 경로의 개수가 됩니다.
Edmonds-Karp를 사용하는 알고리즘의 복잡도는 $O(V^2 V E^2) = O(V^3 E^2)$입니다. 하지만 여기에는 숨겨진 인자가 포함되어 있다는 점에 유의해야 합니다. 모든 소스와 싱크에 대해 최대 흐름 알고리즘이 느리게 동작하는 그래프를 만드는 것은 사실상 불가능하기 때문입니다. 특히 무작위 그래프에서는 알고리즘이 상당히 빠르게 동작합니다.
간선 연결도를 위한 특수 알고리즘¶
간선 연결도를 구하는 문제는 전역 최소 컷을 구하는 문제와 같습니다.
이 문제를 위해 특수한 알고리즘들이 개발되었습니다. 그중 하나는 Stoer-Wagner 알고리즘으로, $O(V^3)$ 또는 $O(V E + V^2 \log V)$ 시간에 동작합니다.
정점 연결도¶
다시 모든 정점 쌍 $s$와 $t$에 대해 반복하면서, 각 쌍에 대해 $s$와 $t$를 분리하는 정점의 최소 개수를 구합니다.
이렇게 하면 앞 절에서 설명한 것과 같은 최대 흐름 접근법을 적용할 수 있습니다.
$x \neq s$이고 $x \neq t$인 각 정점 $x$를 두 정점 $x_1$과 $x_2$로 분할합니다. 이 두 정점을 용량이 $1$인 방향 간선 $(x_1, x_2)$로 연결하고, 모든 간선 $(u, v)$를 용량이 모두 1인 두 방향 간선 $(u_2, v_1)$과 $(v_2, u_1)$로 대체합니다. 그러면 이 구성에 의해 최대 흐름의 값은 $s$와 $t$를 분리하는 데 필요한 정점의 최소 개수와 같아집니다.
이 방법은 간선 연결도를 구하는 흐름 기반 방법과 복잡도가 같습니다.