IT, FIRE, License and Daily life

<순차 검색(sequential search, 선형 검색(linear search)> 

일렬로 된 자료를 처음부터 마지막까지 순서대로 검색하는 방법이다. 가장 간단하고 직접적인 검색 방법이며, 배열이나 연결 리스트로 구현된 순차 자료 구조에서 원하는 항목을 찾는 방법이다.

1. 정렬되지 않은 순차자료구조에서의 순차 검색
[검색 방법]
① 첫 번째 원소부터 시작하여 마지막 원소까지 순서대로 키 값이 일치하는 원소가 있는지를 비교하여 찾는다.
② 키 값이 일치하는 원소를 찾으면 그 원소가 몇 번째 원소인지를 반환한다.
③ 마지막 원소까지 비교하여 키 값이 일치하는 원소가 없으면 찾은 원소가 없는 것이므로 검색 실패
순차 검색 예) 검색 성공의 경우

예) 검색 실패의 경우

[코드]

2. 정렬되어 있는 순차자료구조에서의 순차 검색
[검색 방법]
순서대로 검색하면서 키 값을 비교하여, 원소의 키 값이 찾는 키 값보다 크면 찾는 원소가 없는 것이므로 더 이상 검색을 수행하지 않고 검색종료
정렬되어있는 자료에 대한 순차 검색 예)

[코드]

Copyrightⓒ2014 By 한빛아카데미(주)

<합병 정렬(Merge Sort)>

여러 개의 정렬된 자료의 집합을 병합하여 한 개의 정렬된 집합으로 만드는 방법이다. 부분집합으로 분할(divide)하고, 각 부분집합에 대해서 정렬 작업을 완성(conquer)한 후에 정렬된 부분집합들을 다시 결합(combine)하는 분할 정복(divide and conquer) 기법을 사용한다.

[용어]

1. 분할(divide) : 입력 자료를 같은 크기의 부분집합 2개로 분할한다

2. 정복(conquer) : 부분집합의 원소들을 정렬한다.
부분집합의 크기가 충분히 작지 않으면 순환호출을 이용하여 다시 분할 정복 기법을 적용한다.

3. 결합(combine) : 정렬된 부분집합들을 하나의 집합으로 결합한다.

예)

정렬되지 않은 {69, 10, 30, 2, 16, 8, 31, 22}의 자료들을 병합 정렬 방법으로 정렬하는 과정을 살펴보자.
① 분할 단계 : 정렬할 전체 자료의 집합에 대해서 최소 원소의 부분집합이 될 때까지 분할작업을 반복하여 1개의 원소를 가진 부분집합 8개를 만든다.

② 병합단계 : 2개의 부분집합을 정렬하면서 하나의 집합으로 병합한다. 8개의 부분집합이 1개로 병합될 때까지 반복한다.

[코드]

Copyrightⓒ2014 By 한빛아카데미(주)

<삽입 정렬(insert sort)>

정렬되어있는 부분집합에 정렬할 새로운 원소의 위치를 찾아 삽입하는 방법이다. 

정렬할 자료를 두 개의 부분집합 S와 U로 가정
부분집합 S : 정렬된 앞부분의 원소들
부분집합 U : 아직 정렬되지 않은 나머지 원소들 

정렬되지 않은 부분집합 U의 원소를 하나씩 꺼내서 이미 정렬되어있는 부분집합 S의 마지막 원소부터 비교하면서 위치를 찾아 삽입한다.
삽입 정렬을 반복하면서 부분집합 S의 원소는 하나씩 늘리고 부분집합 U의 원소는 하나씩 감소하게 한다. 부분집합 U가 공집합이 되면 삽입 정렬이 완성된다. 

[삽입 정렬 수행 과정]
정렬되지 않은 {69, 10, 30, 2, 16, 8, 31, 22}의 자료들을 삽입 정렬 방법으로 정렬하는 과정을 살펴보자. 

초기 상태 : 첫 번째 원소는 정렬되어있는 부분 집합 S로 생각하고, 나머지 원소들은 정렬되지 않은 원소들의 부분 집합 U로 생각한다.

S={69} , U={10, 30, 2, 16, 8, 31, 22}

① U의 첫 번째 원소 10을 S의 마지막 원소 69와 비교하여 (10 < 69) 이므로 원소 10은 원소 69의 앞자리가 된다. 더 이상 비교할 S의 원소가 없으므로 찾은 위치에 원소 10을 삽입한다.
S={10, 69} , U={30, 2, 16, 8, 31, 22}

② U의 첫 번째 원소 30을 S의 마지막 원소 69와 비교하여 (30 < 69)이므로 원소 69의 앞자리 원소 10과 비교한다. (30 > 10) 이므로 원소 10과 69 사이에 삽입한다.
•S={10, 30, 69} , U={2, 16, 8, 31, 22}

③ U의 첫 번째 원소 2를 S의 마지막 원소 69와 비교하여 (2 < 69) 이므로 원소 69의 앞자리 원소 30과 비교하고, (2 < 30) 이므로 다시 그 앞자리 원소 10과 비교하는데, (2 < 10) 이면서 더 이상 비교할 S의 원소가 없으므로 원소 10의 앞에 삽입한다.
•S={2, 10, 30, 69} , U={16, 8, 31, 22}

④ 이런 작업을 반복한다.

⑤ U의 첫 번째 원소 22를 S의 마지막 원소 69와 비교하여 (22 < 69)이므로 그 앞자리 원소 31과 비교한다.
(22 < 31) 이므로 그 앞자리 원소 30과 비교하고,
(22 < 30) 이므로 다시 그 앞자리 원소 16과 비교하여,
(22 > 16) 이므로 원소 16과 30 사이에 삽입한다.
•S={2, 8, 10, 16, 22, 30, 31, 69} , U={}

[코드]

Copyrightⓒ2014 By 한빛아카데미(주)

<퀵 정렬(quick sort)>

분할 정렬 방법이며, 정렬할 전체 원소에 대해서 정렬을 수행하지 않고, 기준 값을 중심으로 왼쪽 부분 집합과 오른쪽 부분 집합으로 분할하여 정렬하는 방법이다.
왼쪽 부분 집합에는 기준 값보다 작은 원소들을 이동시키고, 오른쪽 부분 집합에는 기준 값보다 큰 원소들을 이동시킨다.

기준 값 : 피봇(pivot)이란?
일반적으로 전체의 원소 중에서 가운데에 위치한 하나의 원소를 골라서 선택 

퀵 정렬은 다음의 두 가지 기본 작업을 반복 수행하여 완성한다.
1. 분할(divide)
정렬할 자료들을 기준값을 중심으로 2개의 부분 집합으로 분할하기
2. 정복(conquer)
부분 집합의 원소들 중에서 기준값보다 작은 원소들은 왼쪽 부분 집합으로, 기준값보다 큰 원소들은 오른쪽 부분집합으로 정렬하기.
부분 집합의 크기가 1 이하로 충분히 작지 않으면 순환호출을 이용하여 다시 분할.

[퀵 정렬 수행 방법]
- 부분 집합으로 분할하기 위해서 L과 R을 사용
① 왼쪽 끝에서 오른쪽으로 움직이면서 크기를 비교하여 피봇 보다 크거나 같은 원소를 찾아 L로 표시
② 오른쪽 끝에서 왼쪽으로 움직이면서 피봇 보다 작은 원소를 찾아 R로 표시
③ L이 가리키는 원소와 R이 가리키는 원소를 서로 교환한다.
- L와 R이 만나게 되면 피봇과 R의 원소를 서로 교환하고, 교환한 위치를 피봇의 위치로 확정한다.
- 피봇의 확정된 위치를 기준으로 만들어진 새로운 왼쪽 부분 집합과 오른쪽 부분 집합에 대해서 퀵 정렬을 순환적으로 반복 수행하는데 모든 부분 집합의 크기가 1 이하가 되면 퀵 정렬을 종료한다.

[퀵 정렬 수행 과정]
정렬되지 않은 {69, 10, 30, 2, 16, 8, 31, 22}의 자료들을 퀵 정렬 방법으로 정렬하는 과정을 살펴보자. 

원소의 개수가 8개이므로 네 번째 자리에 있는 원소 2를 첫 번째 피봇으로 선택하고 퀵 정렬 시작.

① 원소 2를 피봇으로 선택하고 퀵 정렬 시작.

L이 오른쪽으로 이동하면서 피봇 보다 크거나 같은 원소를 찾고, R은 왼쪽으로 이동하면서 피봇 보다 작은 원소를 찾는다.
L은 원소 69를 찾았지만, R은 피봇 보다 작은 원소를 찾지 못한 채로 원소 69에서 L과 만나게 된다.
L과 R이 만났으므로, 원소 69를 피봇과 교환하여 피봇 원소 2의 위치를 확정한다.

② 피봇 2의 왼쪽 부분 집합은 공집합이므로 퀵 정렬을 수행하지 않고, 오른쪽 부분 집합에 대해서 퀵 정렬 수행.
오른쪽 부분 집합의 원소가 7개 이므로 가운데 있는 원소 16을 피봇으로 선택.

L이 찾은 30과 R이 찾은 8을 서로 교환한다.

현재 위치에서 L과 R의 작업을 반복한다.
L은 원소 69를 찾았지만, R은 피봇 보다 작은 원소를 찾지 못한 채로 원소 69에서 L과 만나게 된다. L과 R이 만났으므로, 원소 69를 피봇과 교환하여 피봇 원소 16의 위치를 확정한다.

③ 이런식으로 반복수행한다.

④ 피봇 30의 확정된 위치에서의 왼쪽 부분 집합의 원소가 한 개 이므로 퀵 정렬을 수행하지 않고, 오른쪽 부분 집합에 대해서 퀵 정렬 수행.
오른쪽 부분 집합의 원소 2개 중에서 원소 31을 피봇으로 선택한다.

L은 오른쪽으로 이동하면서 원소 31을 찾고, R은 왼쪽으로 이동하면서 피봇 보다 작은 원소를 찾다가 못 찾은 채로 원소 31에서 L과 만난다.
L과 R이 만났으므로 피봇과 교환하는데 R의 원소가 피봇이므로 결국 제자리가 확정된다.

피봇 31의 오른쪽 부분 집합의 원소가 한 개 이므로 퀵 정렬을 수행하지 않는다. 이것으로써 전체 퀵 정렬이 모두 완성되었다.

퀵 정렬을 분석해보자.

[메모리 사용공간]
n개의 원소에 대하여 n개의 메모리 사용 

[연산 시간]
1. 최선의 경우
- 피봇에 의해서 원소들이 왼쪽 부분 집합과 오른쪽 부분 집합으로 정확히 n/2개씩 이등분이 되는 경우가 반복되어 수행 단계 수가 최소가 되는 경우
2. 최악의 경우
- 피봇에 의해 원소들을 분할하였을 때 1개와 n-1개로 한쪽으로 치우쳐 분할되는 경우가 반복되어 수행 단계 수가 최대가 되는 경우

평균 시간 복잡도 : O(n log2n)

같은 시간 복잡도를 가지는 다른 정렬 방법에 비해서 자리 교환 횟수를 줄임으로써 더 빨리 실행되어 실행 시간 성능이 좋은 정렬 방법임.

[코드]

Copyrightⓒ2014 By 한빛아카데미(주)

<버블 정렬(bubble sort)>

​인접한 두 개의 원소를 비교하여 자리를 교환하는 방식이다.
첫 번째 원소부터 마지막 원소까지 반복하여 한 단계가 끝나면 가장 큰 원소가 마지막 자리로 정렬된다.
첫 번째 원소부터 인접한 원소끼리 계속 자리를 교환하면서 맨 마지막 자리로 이동하는 모습이 물 속에서 물 위로 올라오는 물방울 모양과 같다고 하여 버블(bubble) 정렬이라 한다. 

[버블 정렬 수행 과정]
정렬되지 않은 {69, 10, 30, 2, 16, 8, 31, 22}의 자료들을 버블 정렬 방법으로 정렬하는 과정을 살펴보자.

① 인접한 두 원소를 비교하여 자리를 교환하는 작업을 첫 번째 원소부터 마지막 원소까지 차례로 반복하여 가장 큰 원소 69를 마지막 자리로 정렬.

② 버블 정렬을 수행하여 나머지 원소 중에서 가장 큰 원소 31을 끝에서 두 번째 자리로 정렬.

③ 이과정을 반복 수행한다. 

④ 버블 정렬을 수행하여 나머지 원소 중에서 가장 큰 원소 8을 끝에서 일곱 번째 자리로 정렬.

버블 정렬을 분석해보자.

[메모리 사용공간]
n개의 원소에 대하여 n개의 메모리 사용 

[연산 시간]
1. 최선의 경우 : 자료가 이미 정렬되어있는 경우
- 비교횟수 : i번째 원소를 (n-i)번 비교하므로, n(n-1)/2 번
- 자리교환횟수 : 자리교환이 발생하지 않음
2. 최악의 경우 : 자료가 역순으로 정렬되어있는 경우
- 비교횟수 : i번째 원소를 (n-i)번 비교하므로, n(n-1)/2 번
−자리교환횟수 : i번째 원소를 (n-i)번 교환하므로, n(n-1)/2 번
평균 시간 복잡도는 O(n2)이 된다.

[코드]

Copyrightⓒ2014 By 한빛아카데미(주)

<선택 정렬(selection sort)>

전체 원소들 중에서 기준 위치에 맞는 원소를 선택하여 자리를 교환하는 방식으로 정렬 

[수행 방법]
1. 전체 원소 중에서 가장 작은 원소를 찾아 선택하여 첫 번째 원소와 자리를 교환한다.
2. 그 다음 두 번째로 작은 원소를 찾아 선택하여 두 번째 원소와 자리를 교환한다.
3. 그 다음에는 세 번째로 작은 원소를 찾아 선택하여 세 번째 원소와 자리를 교환한다.
4. 이 과정을 반복하면서 정렬을 완성한다.

ex) 정렬되지 않은 {69, 10, 30, 2, 16, 8, 31, 22}의 자료들을 선택 정렬 방법으로 정렬하는 과정을 보여라.

① 첫 번째 자리를 기준 위치로 정하고, 전체 원소 중에서 가장 작은 원소 2를 선택하여 기준 위치에 있는 원소 69와 자리 교환

② 두 번째 자리를 기준 위치로 정하고, 나머지 원소 중에서 가장 작은 원소 8을 선택하여 기준 위치에 있는 원소 10과 자리 교환

③ 이런식으로 반복한다.

④ 일곱 번째 자리를 기준 위치로 정하고, 나머지 원소 중에서 가장 작은 원소 31을 선택하여 기준 위치에 있는 원소 31과 자리 교환. (제자리)

선택 정렬을 분석해보자.

1. 메모리 사용공간 - n개의 원소에 대하여 n개의 메모리 사용
2. 비교횟수
1단계 : 첫 번째 원소를 기준으로 n개의 원소 비교
2단계 : 두 번째 원소를 기준으로 마지막 원소까지 n-1개의 원소 비교
3단계 : 세 번째 원소를 기준으로 마지막 원소까지 n-2개의 원소 비교
i 단계 : i 번째 원소를 기준으로 n-i개의 원소 비교

전체 비교횟수는 n(n-1)/2이다. 

즉, 어떤 경우에서나 비교횟수가 같으므로 시간 복잡도는 O(n2)이 된다.

[선택 정렬 코드]

Copyrightⓒ2014 By 한빛아카데미(주)

<정렬(sort)>

​2개 이상의 자료를 작은 것부터 큰 것 순서의 오름차순(ascending)이나 큰 것부터 작은 것 순서의 내림차순(descending)으로 재배열하는 것
키 - 자료를 정렬하는데 사용하는 기준이 되는 특정 값 

[정렬의 예]

<실행 방법에 따른 분류> 

1. 비교식 정렬(comparative sort)
비교하고자 하는 각 키 값들을 한번에 두 개씩 비교하여 교환하는 방식으로 정렬을 실행하는 방법
2. 분산식 정렬(distribute sort)
키 값을 기준으로 하여 자료를 여러 개의 부분 집합으로 분해하고, 각 부분집합을 정렬함으로써 전체를 정렬하는 방식으로 실행하는 방법

<내부 정렬(internal sort)>

​정렬할 자료를 메인 메모리에 올려서 정렬하는 방식
정렬 속도가 빠르지만 정렬할 수 있는 자료의 양이 메인 메모리의 용량에 따라 제한됨 

[내부 정렬 방식]
- 교환 방식 : 키를 비교하고 교환하여 정렬하는 방식 (선택 정렬, 버블 정렬, 퀵 정렬)
- 삽입 방식 : 키를 비교하고 삽입하여 정렬하는 방식(삽입 정렬, 쉘 정렬)
- 병합 방식 : 키를 비교하고 병합하여 정렬하는 방식 (2-way병합, n-way병합)
- 분배 방식 : 키를 구성하는 값을 여러 개의 부분집합에 분배하여 정렬하는 방식 (기수 정렬)
- 선택 방식 : 이진 트리를 사용하여 정렬하는 방식 (히프 정렬, 트리 정렬) 

<외부 정렬(external sort)>

​정렬할 자료를 보조 기억장치에서 정렬하는 방식
대용량의 보조 기억 장치를 사용하기 때문에 내부 정렬보다 속도는 떨어지지만 내부 정렬로 처리할 수 없는 대용량의 자료에 대한 정렬 가능 

[외부 정렬 방식]

- 병합 방식 : 파일을 부분 파일로 분리하여 각각을 내부 정렬 방법으로 정렬하여 병합하는 정렬 방식 (2-way 병합, n-way 병합)

Copyrightⓒ2014 By 한빛아카데미(주)

<깊이 우선 탐색(depth first search : DFS)>

DFS란 스택을 이용하여 그래프를 탐색해 나가는 방법으로써 가능한 깊이 vertex를 들어간뒤 특정 vertex에서 더이상 갈곳이 없으면 그 vertex를 체크한뒤 다시 올라가서 갈 수 있는 모든 vertex를 탐색해나가는 기법이다.

시작 정점의 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색해 가다가 더 이상 갈 곳이 없게 되면, 가장 마지막에 만났던 갈림길 간선이 있는 정점으로 되돌아와서 다른 방향의 간선으로 탐색을 계속 반복하여 결국 모든 정점을 방문하는 순회방법.
가장 마지막에 만났던 갈림길 간선의 정점으로 가장 먼저 되돌아가서 다시 깊이 우선 탐색을 반복해야 하므로 후입선출 구조의 스택 사용.

[깊이 우선 탐색의 수행 순서]

⑴ 시작 정점 v를 결정하여 방문한다.
⑵ 정점 v에 인접한 정점 중에서
① 방문하지 않은 정점 w가 있으면, 정점 v를 스택에 push하고 정점 w를 방문한다. 그리고 w를 v로 하여 다시 ⑵를 반복한다.
② 방문하지 않은 정점이 없으면, 탐색의 방향을 바꾸기 위해서 스택을 pop하여 받은 가장 마지막 방문 정점을 v로 하여 다시 ⑵를 반복한다.
⑶ 스택이 공백이 될 때까지 ⑵를 반복한다.

[알고리즘]

ex)

① 정점 A를 시작으로 깊이 우선 탐색을 시작

visited[A]←true;

② 정점 A에 방문하지 않은 정점 B, C가 있으므로 A를 스택에 push 하고, 인접정점 B와 C 중에서 오름차순에 따라 B를 선택하여 탐색을 계속한다.

push(stack, A);
visited[B]←true;
B 방문;

③ 정점 B에 방문하지 않은 정점 D, E가 있으므로 B를 스택에 push 하고, 인접정점 D와 E 중에서 오름차순에 따라 D를 선택하여 탐색을 계속한다.

push(stack, B);
visited[D]←true;
D 방문;

④ 정점 D에 방문하지 않은 정점 G가 있으므로 D를 스택에 push 하고, 인접정점 G를 선택하여 탐색을 계속한다.

push(stack, D);
visited[G]←true;
G 방문;

⑤ 정점 G에 방문하지 않은 정점 E, F가 있으므로 G를 스택에 push 하고, 인접정점 E와 F 중에서 오름차순에 따라 E를 선택하여 탐색을 계속한다.

push(stack, G);
visited[E]←true;
E 방문;

⑥ 정점 E에 방문하지 않은 정점 C가 있으므로 E를 스택에 push 하고, 인접정점 C를 선택하여 탐색을 계속한다.

push(stack, E);
visited[C]←true;
C 방문;

⑦ 정점 C에서 방문하지 않은 인접정점이 없으므로, 마지막 정점으로 돌아가기 위해 스택을 pop 하여 받은 정점 E에 대해서 방문하지 않은 인접정점이 있는지 확인한다.

pop(stack);

⑧ 정점 E는 방문하지 않은 인접정점이 없으므로, 다시 스택을 pop 하여 받은 정점 G에 대해서 방문하지 않은 인접정점이 있는지 확인한다.

pop(stack);

⑨ 정점 G에 방문하지 않은 정점 F가 있으므로 G를 스택에 push 하고, 인접정점 F를 선택하여 탐색을 계속한다.

push(stack, G);
visited[F]←true;
F 방문;

⑩ 정점 F에서 방문하지 않은 인접정점이 없으므로, 마지막 정점으로 돌아가기 위해 스택을 pop 하여 받은 정점 G에 대해서 방문하지 않은 인접정점이 있는지 확인한다.

pop(stack);

⑪ 정점 G에서 방문하지 않은 인접정점이 없으므로, 다시 마지막 정점으로 돌아가기 위해 스택을 pop 하여 받은 정점 D에 대해서 방문하지 않은 인접정점이 있는지 확인한다.

pop(stack);

⑫ 모두 pop을 한다.

⑬ 현재 정점 A에서 방문하지 않은 인접 정점이 없으므로 마지막 정점으로 돌아가기 위해 스택을 pop하는데, 스택이 공백이므로 깊이 우선 탐색을 종료한다.

2. 너비 우선 탐색(breadth first search : BFS)
−BFS란 큐를 이용하며 그래프를 탐색해 나가는 방법으로, 탐색에 대한 특징은 너비 우선 탐색은 깊이가 1인 모든 정점을 방문하고 나서, 그 다음에는 깊이가 2인 모든 정점을, 깊이가 3인 모든 정점을 방문하는 식으로 계속 방문하다가 더이상 방문할 곳이 없으면 탐색을 마치는 기법이다.

Copyrightⓒ2014 By 한빛아카데미(주)

<인접 행렬(adjacent matrix)>

행렬에 대한 2차원 배열을 사용하는 순차 자료구조 방법이다. 그래프의 두 정점을 연결한 간선의 유무를 행렬로 저장한다.
- n개의 정점을 가진 그래프 : n x n 정방행렬
- 행렬의 행번호와 열번호 : 그래프의 정점
- 행렬 값 : 두 정점이 인접되어있으면 1, 인접되어있지 않으면 0 

무방향 그래프의 인접 행렬 : 행 i의 합 = 열 i의 합 = 정점 i의 차수
방향 그래프의 인접 행렬 : 행 i의 합 = 정점 i의 진출차수, 열 i의 합 = 정점 i의 진입차수 

ex - 1)

G1

ex - 2)

G2

ex - 3)

G3

ex - 4)

[인접 행렬 표현의 단점]
- n개의 정점을 가지는 그래프를 항상 n x n개의 메모리 사용
- 정점의 개수에 비해서 간선의 개수가 적은 희소 그래프에 대한 인접 행렬은 희소 행렬이 되므로 메모리의 낭비 발생

Copyrightⓒ2014 By 한빛아카데미(주)

<그래프(graph)>

선형 자료구조나 트리 자료구조로 표현하기 어려운 多:多의 관계를 가지는 원소들을 표현하기 위한 자료구조
그래프 G
- 객체를 나타내는 정점(vertex)과 객체를 연결하는 간선(edge)의 집합
G = (V, E)
- V는 그래프에 있는 정점들의 집합
- E는 정점을 연결하는 간선들의 집합
그래프사용 예 : 버스노선도, 지하철노선도, 인맥 지도, 길찾기, 최단거리 구하기

<그래프의 종류>

1. 무방향 그래프(undirected graph)
두 정점을 연결하는 간선의 방향이 없는 그래프이며, 정점 Vi와 정점 Vj을 연결하는 간선을 (Vi, Vj)로 표현 - (Vi, Vj)와 (Vj, Vi)는 같은 간선을 의미.
V(G1)={A, B, C, D} E(G1)={(A,B), (A,D), (B,C), (B,D), (C,D)}
V(G2)={A, B, C} E(G2)={(A,B), (A,C), (B,C)}

                                    G1                                  G2

                              G3                                    G4

3. 완전 그래프(complete graph)
각 정점에서 다른 모든 정점을 연결하여 가능한 최대의 간선 수를 가진 그래프이다.
정점이 n개인 무방향 그래프에서 최대의 간선 수 : n(n-1)/2개
정점이 n개인 방향 그래프의 최대 간선 수 : n(n-1)개
완전 그래프의 예
- G5는 정점의 개수가 4개인 무방향 그래프이므로 완전 그래프가 되려면 4(4-1)/2=6개의 간선 연결

- G6은 정점의 개수가 4개인 방향 그래프이므로 완전 그래프가 되려면 4(4-1)=12개의 간선 연결

                                G5                                     G6

4. 부분 그래프(subgraph) : G'
원래의 그래프에서 일부의 정점이나 간선을 제외하여 만든 그래프이다.
그래프 G와 부분 그래프 G'의 관계
V(G')⊆V(G), E(G')⊆E(G)
그래프 G1에 대한 부분 그래프의 예

                                 G1                                          G`

5. 가중 그래프(weight graph) , 네트워크(network)
정점을 연결하는 간선에 가중치(weight)를 할당한 그래프

                               G7                                        G8                        

<​그래프 관련 용어>

​1. 그래프에서 두 정점 Vi과 Vj를 연결하는 간선 (Vi, Vj)가 있을 때, 두 정점 Vi와 Vj를인접(adjacent)되어 있다고 하고,
2. 간선 (Vi, Vj)는 정점 Vi와 Vj에 부속(incident)되어있다고 한다.

ex) 그래프 G1에서 정점 A와 인접한 정점은 B와 D이고, 정점 A에 부속되어 있는 간선은 (A,B)와 (A,D)이다.

                                                    G1

                                                  G3

3. 차수(degree) – 정점에 부속되어있는 간선의 수
ex) 무방향 그래프 G1에서 정점 A의 차수는 2, 정점 B의 차수는 3
방향 그래프의 정점의 차수 = 진입차수 + 진출차수
- 방향 그래프의 진입차수(in-degree) : 정점을 머리로 하는 간선의 수
- 방향 그래프의 진출차수(out-degree) : 정점을 꼬리로 하는 간선의 수
- 방향 그래프 G3에서 정점 B의 진입차수는 1, 진출차수는 2
정점 B의 전체 차수는 (진입차수 + 진출차수) 이므로 3이 된다.

4. 경로(path) - 그래프에서 간선을 따라 갈 수 있는 길을 순서대로 나열한 것 즉, 정점 Vi에서 Vj까지 간선으로 연결된 정점을 순서대로 나열한 리스트
ex) 그래프 G1에서 정점 A에서 정점 C까지의 경로 : A-B-C 경로, A-B-D-C 경로, A-D-C 경로, A-D-B-C 경로

5. 경로길이(path length) - 경로를 구성하는 간선의 수

6. 단순경로(simple path) - 모두 다른 정점으로 구성된 경로
ex) 그래프 G1에서 정점 A에서 정점 C까지의 경로 A-B-C는 단순경로이고, 경로 A-B-D-A-B-C는 단순경로가 아니다.

7. 사이클(cycle) - 단순경로 중에서 경로의 시작 정점과 마지막 정점이 같은 경로
ex) 그래프 G1에서 단순경로 A-B-C-D-A는 사이클이 된다.

8. DAG(directed acyclic graph) - 방향 그래프이면서 사이클이 없는 그래프 

9. 연결 그래프(connected graph) - 서로 다른 모든 쌍의 정점들 사이에 경로가 있는 그래프 즉, 떨어져있는 정점이 없는 그래프
그래프에서 두 정점 Vi에서 Vj까지의 경로가 있으면 정점 Vi와 Vj가 연결(connected)되었다고 한다. 

10. 트리는 사이클이 없는 연결 그래프이다.

Copyrightⓒ2014 By 한빛아카데미(주)