동적 연결성 편집하기

동적 연결성(dynamic connectivity)은 그래프 이론에서 시간에 따라 간선이 추가되거나 삭제되는 그래프 상에서 임의의 두 정점이 연결되어 있는지를 효율적으로 판단하는 문제를 의미한다.
==개요==
정적인 그래프에서의 연결성 판단은 DFS나 BFS를 통해 비교적 간단하게 처리할 수 있지만, 그래프가 시간에 따라 변화하는 경우에는 매번 전체 탐색을 수행하는 것은 비효율적이다. 동적 연결성 문제는 이러한 동적인 그래프 환경에서 효율적으로 연결 여부를 판단하고 유지하기 위한 알고리즘과 자료구조를 연구하는 분야이다. 이 문제는 다양한 응용에서 중요하게 등장하며, 특히 온라인 알고리즘, 네트워크 분석, 실시간 시뮬레이션 등에 활용된다.
==문제 유형==
동적 연결성 문제는 간선의 삽입과 삭제 여부에 따라 다음과 같이 나눌 수 있다.
*'''증분 연결성(incremental connectivity)''': 간선의 삽입만 허용되고 삭제는 없음
*'''감소 연결성(decremental connectivity)''': 간선의 삭제만 허용되고 삽입은 없음
*'''완전 동적 연결성(fully dynamic connectivity)''': 간선의 삽입과 삭제가 모두 허용됨
이 중 완전 동적 연결성 문제는 가장 일반적이면서도 어려운 문제로, 이 경우에는 정점 쌍 (u, v)에 대해 항상 "u와 v가 연결되어 있는가?"라는 질의에 빠르게 응답할 수 있는 자료구조가 필요하다.
==알고리즘 및 자료구조==
동적 연결성 문제를 해결하기 위한 대표적인 알고리즘 및 자료구조는 다음과 같다.
*'''서로소 집합(Disjoint-Set, Union-Find)''': 증분 연결성 문제에서 매우 효율적이며, 각 질의에 대해 거의 O(1)의 시간 복잡도를 제공함
*'''동적 트리 자료구조(Dynamic Tree, 예: 링크-컷 트리(Link/Cut Tree), Euler Tour Tree)''': 완전 동적 연결성 문제를 처리할 수 있음
*'''SPQR 트리''', '''탐색 기반 감시 알고리즘''' 등도 제한된 상황에서 활용됨
==시간 복잡도==
*서로소 집합(Union-Find) 구조는 경로 압축과 랭크 기반 병합을 활용할 경우 삽입과 질의 연산 모두에 대해 거의 상수 시간인 O(α(n))을 달성할 수 있다.
*완전 동적 연결성을 처리하는 고급 자료구조(예: Euler Tour Tree)는 O(log² n) 혹은 O(log n) 시간에 삽입, 삭제, 연결성 판별 연산을 지원한다.
==응용==
동적 연결성은 다음과 같은 실용적인 문제에 응용된다.
*네트워크 유지 보수 및 장애 감지
*실시간 시뮬레이션에서의 객체 충돌 상태 추적
*동적인 도로망에서의 길 찾기 알고리즘
*소셜 네트워크에서의 사용자 관계 변화 추적
*버전 관리 시스템의 브랜치 병합 분석
==파이썬 예제: Union-Find를 활용한 증분 연결성==
<syntaxhighlight lang="python">
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        xroot = self.find(x)
        yroot = self.find(y)
        if xroot != yroot:
            self.parent[yroot] = xroot

    def connected(self, x, y):
        return self.find(x) == self.find(y)

# 사용 예시
uf = UnionFind(5)
uf.union(0, 1)
uf.union(1, 2)
print(uf.connected(0, 2))  # True
print(uf.connected(0, 3))  # False
</syntaxhighlight>
==같이 보기==
*[[서로소 집합]]
*[[그래프]]
*[[크루스칼 알고리즘]]
*[[링크-컷 트리]]
*[[네트워크]]
==참고 문헌==
*Robert E. Tarjan, "Efficiency of a Good But Not Linear Set Union Algorithm", Journal of the ACM, 1975.
*D. D. Sleator and R. E. Tarjan, "A Data Structure for Dynamic Trees", Journal of Computer and System Sciences, 1983.
*Thomas H. Cormen et al., ''Introduction to Algorithms'', MIT Press.
==각주==
[[분류:그래프 이론]]