정의
경로 그래프(영어: path graph)는 그래프 이론에서, 정점들이 직선 형태로 연결되어 있는 특수한 형태의 그래프를 말한다. 이 그래프는 단순 경로(simple path)로 구성되며, 모든 정점이 최대 두 개의 변에 연결되어 있다. 양 끝 정점은 각각 하나의 변에만 연결되고, 그 사이의 정점들은 두 개의 변에 연결된다.
개요
경로 그래프는 일반적으로 $ P_n $으로 표기되며, 여기서 $ n $은 그래프에 포함된 정점의 수를 의미한다. 예를 들어, $ P_4 $는 네 개의 정점이 일렬로 연결된 그래프를 나타낸다. 경로 그래프는 트리의 일종이며, 사이클을 포함하지 않으며 연결된 구조를 가진다. 또한, 최단 경로 탐색, 네트워크 구조 분석, 알고리즘 설계 등 다양한 컴퓨터 과학 및 수학 분야에서 기초적인 구조로 활용된다.
어원/유래
'경로 그래프'라는 용어는 영어 "path graph"의 번역어로, "path"는 수학에서 점들이 순차적으로 이어진 구조를 의미하며, 이는 그래프 이론에서 정점들이 변을 통해 연결된 순서를 일컫는다. "Graph"는 조합론 및 순수수학에서 점(정점)과 선(변)으로 구성된 구조를 의미한다. 이 용어는 20세기 초반의 그래프 이론 발전 과정에서 정립되었으며, 특히 덴마크의 수학자 헤르하르트 케르베(Harary) 등의 저서에서 정형화된 용어로 자리 잡았다.
특징
- 경로 그래프는 항상 연결 그래프이며, 사이클을 포함하지 않는다.
- $ P_n $에는 $ n $개의 정점과 $ n-1 $개의 변이 존재한다.
- 두 끝 정점(단말 정점)의 차수는 1이며, 나머지 내부 정점의 차수는 2이다.
- 이분 그래프이며, 색칠 수는 2이다.
- 트리의 일종으로, 최소한의 연결성을 유지하는 선형 구조를 가진다.
- 이진 트리나 체인 구조의 모델링에 활용되기도 한다.
관련 항목
- 그래프 이론
- 트리 (graph theory)
- 사이클 그래프
- 완전 그래프
- 연결성 (graph connectivity)
- 정점 (vertex) 및 변 (edge)