경로 그래프

P_{6}

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

정의

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

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

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

v_{i} v_{j} \in E (P_{n}) ⟺ i = j \pm 1 (i, j = 1, \dots, n)

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

V (P_{\infty}) = ℤ

m n \in E (P_{\infty}) ⟺ m - n = \pm 1 (m, n \in ℤ)

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

L (P_{n}) = P_{n - 1} (n > 0)

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

χ (P_{n}) = \min {2, n}

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