경로 그래프(經路 graph, 영어: path graph)는 그래프 이론에서 사용되는 기본적인 그래프의 한 종류이다. 경로 그래프는 모든 꼭짓점의 차수가 2 이하인 나무(tree)이며, 일렬로 늘어선 형태를 가진다.
정의
경로 그래프 $P_n$은 $n$개의 꼭짓점(vertex)을 가지는 그래프로, 꼭짓점들을 $v_1, v_2, \dots, v_n$의 순서로 나열하였을 때 변(edge)은 ${v_i, v_{i+1}}$ ($i = 1, 2, \dots, n-1$)로만 구성된다. 즉, 각 꼭짓점이 직선 형태로 연결되어 있으며, 양 끝의 두 꼭짓점은 차수(degree)가 1이고, 나머지 중간 꼭짓점들은 차수가 2이다.
무한 경로 그래프 $P_\infty$는 가산 무한개(countably infinite)의 꼭짓점을 가지며, 정수 집합 $\mathbb{Z}$를 꼭짓점으로 하고 인접한 정수 사이에 변이 존재하는 그래프로 정의된다.
성질
- 경로 그래프 $P_n$은 $n$개의 꼭짓점과 $n-1$개의 변을 가진다.
- 경로 그래프의 선 그래프(line graph)는 크기가 1 작은 경로 그래프이다: $L(P_n) = P_{n-1}$ ($n > 0$).
- 경로 그래프의 색칠수(chromatic number)는 $\chi(P_n) = \min{2, n}$으로, $n \ge 2$일 때 2이다. 즉, 경로 그래프는 이분 그래프(bipartite graph)이다.
- 경로 그래프는 나무(tree)의 일종이며, 따라서 연결 그래프(connected graph)이다.
- 반지름(radius)은 $\lfloor n/2 \rfloor$, 지름(diameter)은 $n-1$이다.
- 자기동형군(automorphism group)의 크기는 2이다(좌우 대칭).
표기
경로 그래프는 보통 $P_n$으로 표기하며, 여기서 $n$은 꼭짓점의 개수를 의미한다. 일부 문헌에서는 $n$이 변의 개수를 의미하기도 하므로 주의가 필요하다.
응용
경로 그래프는 다른 그래프의 부분 그래프(subgraph)로서 자주 등장하며, 이때 해당 그래프에서의 경로(path)라고 불린다. 또한 대수학에서는 A형 딘킨 도표(Dynkin diagram)로 나타나며, A형 근계(root system)와 A형 바일 군(Weyl group, 즉 대칭군)을 분류하는 역할을 한다.
