경로 그래프

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

경로 그래프

정의편집

경로 그래프   개의 꼭짓점을 가지는 그래프이다.

 

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

 

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

 
 

성질편집

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

 

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

 

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

외부 링크편집

같이 보기편집