도달성

그래프 이론에서 도달성, 도달 가능성(reachability)은 그래프 안의 하나의 꼭짓점에서 다른 꼭짓점으로 도달할 수 있는 가능성을 말한다. $s$ 로 시작하고 $t$ 로 끝나는 인접한 일련의 꼭짓점(예: 경로)이 있다면 꼭짓점 $s$ 는 꼭짓점 $t$ 에 도달할 수 있다.(그리고 $t$ 는 $s$ 로부터 도달이 가능하다)

방향이 없는(무향) 그래프에서 한 쌍의 꼭짓점 간의 도달성은 그래프의 연결 요소를 식별함으로써 결정할 수 있다. 이러한 그래프에서 임의의 쌍의 꼭짓점들은 동일한 연결 요소에 속해 있을 경우 서로에게 도달할 수 있다. 무향 그래프의 연결 요소는 선형 시간에서 식별이 가능하다.

정의 편집

유향 그래프 $G=(V,E)$ (꼭짓점 집합 $V$ 와 간선 집합 $E$ 포함)의 경우 $G$ 의 도달성 관계는 $E$ 의 전이 폐쇄이며 $V$ 내의 꼭짓점의 모든 순서쌍의 집합 $(s,t)$ 으로 이야기할 수 있는데 이를 위해 일련의 꼭짓점 $v_{0}=s,v_{1},v_{2},...,v_{k}=t$ 가 존재하며 이처럼 간선 $(v_{i-1},v_{i})$ 은 모든 $1\leq i\leq k$ 에 대해 $E$ 에 속한다.^[1]

$G$ 가 비순환이면 도달 관계는 부분 순서로 된다. 이러한 방식으로 어떠한 부분 순서로도 정의할 수 있는데, 이를테면 이행성 감소(transitive reduction)의 도달 관계를 들 수 있다.^[2]

각주 편집

↑ Skiena, Steven S. (2011), 〈15.5 Transitive Closure and Reduction〉, 《The Algorithm Design Manual》 2판, Springer, 495–497쪽, ISBN 9781848000698 .
↑ Cohn, Paul Moritz (2003), 《Basic Algebra: Groups, Rings, and Fields》, Springer, 17쪽, ISBN 9781852335878 .

[skiena-1] Skiena, Steven S. (2011), 〈15.5 Transitive Closure and Reduction〉, 《The Algorithm Design Manual》 2판, Springer, 495–497쪽, ISBN 9781848000698 .

[2] Cohn, Paul Moritz (2003), 《Basic Algebra: Groups, Rings, and Fields》, Springer, 17쪽, ISBN 9781852335878 .

[1]

[2]