[레포트] 이산수학 Assignment#8

목차

1.진위 문제
2.선택 문제
3.주관식 문제

본문내용

Part 1. 진위 문제
다음 문장의 진위를 판단하고, 틀린 경우에는 그 이유를 적으시오.

2) 어떤 노드의 차수는 그 노드의 서브 트리의 개수를 나타낸다.
- (o)

4) 트리에서 어느 한 연결선만 첨가하더라도 사이클을 형성하게 된다.
- (o) 트리는 연결되어 있고 사이클이 없는 그래프로서 어느 한 연결선만 첨가하더라도 사이클을 형성하게 된다.

6) 이진 트리에서 중간 노드는 항상 두 개의 자식 노드를 가진다.
- (x) 포화 이진 트리가 아니라면 중간 노드는 1개 또는 2개의 자식 노드를 가질 수 있다.

8) 이진 트리를 표현할 경우에는 배열에 의한 방법이 훨씬 편리하다.
- (x) 배열에 의한 방법은 트리의 중간에 새로운 노드를 삽입하거나 기존의 노드를 지울 경우 비효율적이다. 따라서 여기서는 일반적으로 가장 많이 쓰이고 있는 연결 리스트에 의한 방법이 훨씬 편리하다.

10) 최소 비용 생성 트리를 구하는 방법으로는 프림의 알고리즘과 크루스칼의 알고리즘이 있다.
- (o) 최소 이용 생성 트리의 대표적인 2가지 방법은 프림(Prim)의 알고리즘과 크루스칼(Kruskal)의 알고리즘이다.

Part 2. 선택 문제
2) 다음의 그래프 중 트리에 해당하지 않은 것은?
- (3) 모든 노드들이 적어도 한 개의 연결선을 갖는 (1), (2), (4)와는 달리 (3)은 연결선이 한개도 없는 노드가 존재한다. 고로 (3)은 트리가 아니다.

4) 다음 중 다른 세 개와 동치가 아닌 것은 어느 것인가?
(1) G는 트리이다.
(2) G는 이진 트리이다.
(3) G는 사이클을 가지지 않으며 m=n-1이다.
(4) G는 연결되어 있고 m=n-1이다.
- (2) 그래프 G=(V,E)에서 lVl=n 이고 lEl=m일 때 다음의 문장들은 모두 동치이다.
(1) G는 트리이다.
(2) G는 연결되어 있고 m=n-1이다.
(3) G는 연결되어 있고 어느 한 연결선만을 제거하더라도 G는 연결되지 않는다.
(4) G는 사이클을 가지지 않으며 m=n-1이다.
(5) G는 어느 한 연결선만 첨가하더라도 사이클을 형성하게 된다.
그러므로 (2)는 다른 세 개와 동치가 아니다.

참고 자료

없음