경로 (그래프 이론) 문서 원본 보기

{{위키데이터 속성 추적}}
[[그래프 이론]]에서 '''경로'''(經路, {{llang|en|path|패스}})는 같은 [[꼭짓점]]을 거듭 거치지 않는 변들의 열이다.

[[유향 그래프]]에서 '''유향 경로''' 또는 '''방향 경로''', '''디패스'''(dipath<ref>Graph Structure Theory: Proceedings of the AMS-IMS-SIAM Joint Summer Research Conference on Graph Minors, Held June 22 to July 5, 1991,, [https://books.google.com/books?id=idigH5CTGWAC&pg=PA205 p.205]</ref>, 다이패스)는 간선이 모두 같은 방향을 향하는 제약이 있는, 일련의 꼭짓점을 연결하는 일련의 간선들이다.

'''단순 경로'''는 경로 내 중복된 정점이 없는 경로를 말한다.

== 정의 ==
[[그래프]] <math>G</math>의, 길이 <math>n\in\mathbb N</math>의 '''유한 경로'''는 다음 성질을 만족시키는 <math>V(G)</math> 속의 [[점렬]] <math>v_0,v_1,\dots,v_n</math>이다.
* 모든 <math>i,j=0,\dots,n</math>에 대하여, <math>v_i=v_j</math>라면 <math>i=j</math>이다.
* 모든 <math>i=0,\dots,n-1</math>에 대하여, <math>v_iv_{i+1}\in E(G)</math>이다.
[[그래프]] <math>G</math>의 '''무한 경로'''는 다음 성질을 만족시키는 <math>V(G)</math> 속의 무한 [[점렬]] <math>v_0,v_1,\dots</math>이다.
* 모든 <math>i,j=0,\dots</math>에 대하여, <math>v_i=v_j</math>라면 <math>i=j</math>이다.
* 모든 <math>i=0,\dots</math>에 대하여, <math>v_iv_{i+1}\in E(G)</math>이다.
'''경로'''는 유한 경로 또는 무한 경로이다.

정의에 따라, 경로는 같은 [[꼭짓점]]을 중복해서 거칠 수 없다. [[한붓그리기]]와 같이 꼭짓점을 중복하지만 변이 중복되지 않는 경우를 '''트레일'''({{llang|en|trail}})이라고 하고, 변 또한 중복될 수 있는 경우 '''보행'''(步行, {{llang|en|walk}})이라고 한다.

== 예 ==
다음과 같은 그래프를 살펴보자.
:[[파일:Graph cycle.svg|200px]]
여기서 HAB와 HDG는 경로이다. BDEFDC는 꼭짓점 D가 반복되므로 경로가 아니지만 트레일이다. BDEFDB는 변 BD가 반복되므로 트레일이 아니지만 보행이다.

== 알고리즘 ==
{{본문|최단 경로 문제}}
두 꼭짓점 사이의 최장·최단 경로를 찾는 문제를 생각해 볼 수 있다. P≠NP를 가정하면, 최단 경로를 찾는 것은 최장 경로를 찾는 것보다 더 쉬우며, [[데이크스트라 알고리즘]]을 사용할 수 있다.

== 같이 보기 ==
* [[경로 그래프]]
* [[순환 (그래프 이론)]]
* [[경로 (위상수학)]]

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

== 외부 링크 ==
* {{매스월드|id=GraphPath|title=Graph path}}
* {{매스월드|id=Trail|title=Trail}}
* {{매스월드|id=Walk|title=Walk}}

{{전거 통제}}

[[분류:그래프 이론]]