도달성 문서 원본 보기

{{위키데이터 속성 추적}}
[[그래프 이론]]에서 '''도달성''', '''도달 가능성'''(reachability)은 그래프 안의 하나의 [[꼭짓점 (그래프 이론)|꼭짓점]]에서 다른 꼭짓점으로 도달할 수 있는 가능성을 말한다. <math>s</math>로 시작하고 <math>t</math>로 끝나는 [[그래프 이론 용어|인접]]한 일련의 꼭짓점(예: [[그래프 이론 용어|경로]])이 있다면 꼭짓점 <math>s</math>는 꼭짓점 <math>t</math>에 도달할 수 있다.(그리고 <math>t</math>는 <math>s</math>로부터 도달이 가능하다)

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

== 정의 ==
유향 그래프 <math>G = (V, E)</math>(꼭짓점 집합 <math>V</math>와 간선 집합 <math>E</math> 포함)의 경우
<math>G</math>의 도달성 [[이항관계|관계]]는 <math>E</math>의 [[전이 폐쇄]]이며 <math>V</math> 내의 꼭짓점의 모든 순서쌍의 집합 <math>(s,t)</math>으로 이야기할 수 있는데 이를 위해 일련의 꼭짓점 <math>v_0 = s, v_1, v_2, ..., v_k = t</math>가 존재하며 이처럼 간선 <math>(v_{i-1},v_i)</math>은 모든 <math>1 \leq i \leq k</math>에 대해 <math>E</math>에 속한다.<ref name="skiena">{{인용
 | last = Skiena | first = Steven S.
 | contribution = 15.5 Transitive Closure and Reduction
 | edition = 2nd
 | isbn = 9781848000698
 | pages = 495–497
 | publisher = Springer
 | title = The Algorithm Design Manual
 | url = https://books.google.com/books?id=7XUSn0IKQEgC&pg=PA495
 | year = 2011}}.</ref>

<math>G</math>가 [[유향 비순환 그래프|비순환]]이면 도달 관계는 [[부분 순서 집합|부분 순서]]로 된다. 이러한 방식으로 어떠한 부분 순서로도 정의할 수 있는데, 이를테면 [[이행성 감소]](transitive reduction)의 도달 관계를 들 수 있다.<ref>{{인용
 | last = Cohn | first = Paul Moritz
 | isbn = 9781852335878
 | page = 17
 | publisher = Springer
 | title = Basic Algebra: Groups, Rings, and Fields
 | url = https://books.google.com/books?id=VESm0MJOiDQC&pg=PA17
 | year = 2003}}.</ref>

== 각주 ==
{{각주}}

{{전거 통제}}

[[분류:그래프 연결]]