트리와 그래프에 관한 레포트

소개

과제로 하긴 했지만, 시험공부용으로도 손색없는 좋은 레포트입니다.

당연히 A+ 받았습니다.

목차

가. 개요

나. 그래프

1. 그래프의 정의

2. 그래프의 용어

3. 그래프의 분류

4. 그래프의 표현 방법

5. 그래프의 탐색

6. 그래프의 응용

다. 트리

1. 트리의 정의

2. 트리의 조건

3. 트리의 용어

4. 트리의 분류

5. 트리의 표현 방법

6. 트리의 탐색

7. 트리의 응용

라. 레포트를 작성하며

본문내용

트리는 대표적인 비선형 자료구조로 일상생활의 많은 부분에서 쓰인다. 또한 자료구조로서의 트리가 아니더라도 많은 부분이 트리와 같은 형태의 표기를 채택하는데, 일반적인 예로 회사의 조직도를 들 수 있다. 트리와 마찬가지로 대표적인 비선형 자료구조로 그래프를 꼽을 수 있는데. 트리와 개념상 매우 유사하기 때문에 트리와 그래프를 같이 익힌다면 큰 도움이 될 것 같아 트리를 조사하면서 그래프도 같이 조사하게 되었다. 트리와 마찬가지로 그래프의 정의와 특성, 종류등을 알아보고 트리의 탐색과 개념상 매우 비슷한 그래프에서의 탐색도 비중있게 다루어 본다. 그리고 우리가 궁극적으로 알고자 하는 트리라는 것이 무엇이며. 어떤 종류의 트리가 존재하는지. 어떤 특성을 나타내는지 알아보고 이를 응용하여 생활에서 사용되는 트리의 예를 알아보도록 한다.
나. 그래프
1. 그래프의 정의
그래프(graph)는 그래프 이론에서 다루는 수학 용어이다. 그래프는 꼭짓점(vertex)과 변(edge)으로 이루어져 있는데, 흔히 그래프를 꼭짓점의 집합과 두 꼭짓점을 잇는 변의 집합의 순서쌍으로 정의한다. 변에 방향을 허용하느냐 마느냐에 따라서 방향이 있는 그래프, 혹은 방향이 없는 그래프로 나뉘는데 그래프의 변이 방향을 가지고 있으면 유향 그래프(directed graph)라고 하며 반대로 변이 방향을 가지고 있지 않은 경우는 무향 그래프(undirected graph)라고 한다. 그래프 이론을 연구하는 사람들은 이렇게 다양한 형태의 그래프가 가지는 특성을 연구하고, 이를 컴퓨터 네트워크와 같은 다른 분야에 적용하기도 한다.
<그림 1>그래프의 예
그래프에서 노드는 `vertex`, 링크는 `edge`라 하며, 하나의 그래프는 다음과 같이 vertex와 edge의 집합으로 정의할 수 있다. 이 그림은 각 도시를 표현하는 단위 노드들을 링크로 연결한 것이다. 링크는 두 개의 노드를 연결하여 링크의 양 끝 노드가 서로 특정한 관계를 가지고 있음을 나타내며 <그림 1>에서의 링크는 두 도시를 연결하는 도로가 있음을 표현해준다.
2. 그래프의 용어
차수 : 무향 그래프에서, 한 꼭지점에 이어져있는 변의 개수
유향 그래프에서의 차수
●내차수(인입치수, in-degree) : 한 vertex로 들어오는 edge의 수
●외차수(인출치수(out-degree) : 한 vertex로부터 나가는 edge의 수
인접
●무향 그래프의 인접성 : 두 개의 vertex가 edge로 연결되어 있으면 인접해 있다고 한다.
●유향 그래프의 인접성 : 두 개의 vertex가 edge로 연결되어 있을 때, edge의 방향에 따라 `~로 인접해있다`, `~로부터 인접해있다`고 한다.
<그림 2>무향 그래프의 인접성
A는 B와 인접해있다 / A는 C와 인접해있다

참고자료

· 없음