경로 그래프

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

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

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

성질

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

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

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

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

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

외부 링크

• 틀:매스월드

같이 보기

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