경로 그래프 문서 원본 보기

{{위키데이터 속성 추적}}
[[파일:Path-graph.svg|섬네일|right|경로 그래프 <math>P_6</math>]]
[[그래프 이론]]에서 '''경로 그래프'''(經路graph, {{llang|en|path graph}})는 모든 꼭짓점의 차수가 2 이하인 [[나무 (그래프 이론)|나무]]이다.

== 정의 ==
'''경로 그래프''' <math>P_n</math>은 <math>n</math>개의 꼭짓점을 가지는 그래프이다.
:<math>V(P_n)=\{v_1,\dots,v_n\}</math>
경로 그래프의 변들은 다음과 같다.
:<math>v_iv_j\in E(P_n)\iff i=j\pm1\qquad(i,j=1,\dots,n)</math>

'''무한 경로 그래프''' <math>P_\infty</math>는 [[가산 무한]] 개의 꼭짓점을 갖는다. 이를 편의상 [[정수]]의 집합으로 나타내면, 그 변들은 다음과 같다.
:<math>V(P_\infty)=\mathbb Z</math>
:<math>mn\in E(P_\infty)\iff m-n=\pm1\qquad(m,n\in\mathbb Z)</math>

== 성질 ==
경로 그래프 <math>P_n</math>은 <math>n</math>개의 꼭짓점과 <math>n-1</math>개의 변을 갖는다. 경로 그래프의 [[선 그래프]]는 크기가 1 작은 선 그래프이다.
:<math>L(P_n)=P_{n-1}\qquad(n>0)</math>

경로 그래프의 [[색칠수]]는 다음과 같다.
:<math>\chi(P_n)=\min\{2,n\}</math>
경로 그래프는 [[나무 (그래프 이론)|나무]]를 이루며, 따라서 [[연결 그래프]]이다.

== 외부 링크 ==
* {{매스월드|id=PathGraph|title=Path graph}}

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

[[분류:그래프]]