[이산수학]노드와 변에 대한 정리/트리에 대한 정리_예제포함

[이산수학]노드와 변에 대한 정리/트리에 대한 정리 

 

 

■ 노드와 변에 대한 정리

트리에서 노드의 개수를 v, 변의 개수를 e라고 하면,  e = v - 1 입니다. 

 

예제

(1) 노드의 수가 16개인 트리에 존재하는 변의 수는?

(2) 변의 수가 24개인 트리에 존재하는 노드의 수는?

 

풀이

예제풀이

(1) 15개

(2) 25개

■ 트리에 대한 정리 

n개의 꼭짓점을 갖는 연결 그래프T에 대해 다음은 동치입니다. 

1. T는 트리다

2. T의 변의 수는 n - 1개다. 

3. T에서 변 하나를 제거하면 연결 그래프가 아니다.

4. T에 속하는 서로 다른 꼭짓점 w, v에 대해, w에서 v로 가는 유일한 경로가 존재한다. 

 

수학으로 이해하는 디지털 논리 이산수학 359p 참고

 

-----------------------------------

이산수학 총정리

목록 보러가기 

-----------------------------------