나무 그래프: 두 판 사이의 차이

* 임의의 두 꼭짓점 <math>v_1,v_2\in V(T)</math>에 대하여, <math>v_1</math>과 <math>v_2</math> 사이의 [[경로 (그래프 이론)|경로]]의 수는 1 이하이다.

* <math>T</math>는 [[완전 그래프]] <math>K_3</math>를 [[마이너 (그래프 이론)|마이너]]로 갖지 않는다.

 

(단순 무향) 그래프에 대하여 다음 조건들이 서로 [[동치]]이며, 이 조건을 만족시키는 그래프 <math>T</math>를 '''나무'''라고 한다.

* <math>T</math>는 연결 숲이다.

* 임의의 두 꼭짓점 <math>v_1,v_2\in V(T)</math>에 대하여, <math>v_1</math>과 <math>v_2</math> 사이의 [[경로 (그래프 이론)|경로]]가 정확히 하나 존재한다.

* 임의의 변 <math>e\in E(T)</math>을 지운 그래프 <math>T-e</math>는 연결 그래프가 아니다.