경로 그래프

그래프 이론에서 경로 그래프(經路graph, 영어: path graph)는 모든 꼭짓점의 차수가 2 이하인 나무이다.

경로 그래프 ${\displaystyle P_{6}}$

정의

경로 그래프 ${\displaystyle P_{n}}$은 ${\displaystyle n}$개의 꼭짓점을 가지는 그래프이다.

${\displaystyle V(P_{n})=\{v_{1},\dots ,v_{n}\}}$

경로 그래프의 변들은 다음과 같다.

${\displaystyle v_{i}v_{j}\in E(P_{n})\iff i=j\pm 1\qquad (i,j=1,\dots ,n)}$

무한 경로 그래프 ${\displaystyle P_{\infty }}$는 가산 무한 개의 꼭짓점을 갖는다. 이를 편의상 정수의 집합으로 나타내면, 그 변들은 다음과 같다.

${\displaystyle V(P_{\infty })=\mathbb {Z} }$

${\displaystyle mn\in E(P_{\infty })\iff m-n=\pm 1\qquad (m,n\in \mathbb {Z} )}$

성질

경로 그래프 ${\displaystyle P_{n}}$은 ${\displaystyle n}$개의 꼭짓점과 ${\displaystyle n-1}$개의 변을 갖는다. 경로 그래프의 선 그래프는 크기가 1 작은 선 그래프이다.

${\displaystyle L(P_{n})=P_{n-1}\qquad (n>0)}$

경로 그래프의 색칠수는 다음과 같다.

${\displaystyle \chi (P_{n})=\min\{2,n\}}$

경로 그래프는 나무를 이루며, 따라서 연결 그래프이다.

외부 링크

• Weisstein, Eric Wolfgang. “Path graph”. 《Wolfram MathWorld》 (영어). Wolfram Research.

같이 보기

• 경로 (그래프 이론)
• 순환 그래프