기록보관

 그래프 모양이 나무를 거꾸로 세워놓은 것처럼 생겼다고 하여 불리는 이름인 트리(Tree)또는 수형도는 그래프의 특별한 형태로서 컴퓨터를 통한 자료 처리와 응용에 매우 중요한 역할을 한다.

트리: 하나 이상의 노드로 구성된 유한 집합으로서 2가지 조건 만족
 ⑴ 특별히 지정된 노드인 루트(root) 존재
 ⑵ 나머지 노드들은 다시 각각 트리이면서 연결되지 않는 서브 트리(subtree) T₁, T₂, …, Tₙ (n >= 0) 으로 이루어짐
 → n개의 노드를 가진 트리는 n - 1개의 연결선 보유
 → 그래프 G = (V, E)에서 |V| = n이고 |E| = m일 때 다음의 문장들은 모두 동치
     ① G는 트리
     ② G는 연결되어 있고 m = n - 1
     ③ G는 연결되어 있고 어느 한 연결선만을 제거하더라도 연결되지 않음
     ④ G는 사이클을 가지지 않으며 m = n - 1
     ⑤ G는 어느 한 연결선만 추가하더라도 사이클을 형성하게 됨

n-트리(n-ary tree): 모든 중간 노드들이 최대 n개의 자식 노드를 가질 때, n이 2인 경우를 이진 트리(binary tree)라고 함
 → 이진 트리는 공집합이거나, 루트와 좌측 서브 트리, 우측 서브 트리로 이루어짐
 → 이진 트리가 레벨 i에서 가질 수 있는 최대한의 노드 수는 2^i개이며, 높이가 k인 이진 트리가 가질 수 있는 최대한의 전체 노드 수는 (2^k+1) - 1이다. 

⑴ 전순위 탐방(preorder traversal): 루트에서 시작
     ① 노드를 탐방하고 데이터를 프린트
     ② 트리의 좌측 서브트리 탐방
     ③ 트리의 우측 서브트리 탐방

⑵ 중순위 탐방(inorder traversal): 루트에서 시작
     ① 트리의 좌측 서브트리 탐방
     ② 노드를 방문하고 데이터를 프린트
     ③ 트리의 우측 서브트리 탐방

⑶ 후순위 탐방(postorder traversal): 루트에서 시작
     ① 트리의 좌측 서브트리 탐방
     ② 트리의 우측 서브트리 탐방
     ③ 노드를 탐방하고 데이터를 프린트

생성 트리(spanning tree): 어떤 그래프에서 모든 노드들을 포함하는 트리
 → 생성 트리의 비용은 트리 연결선의 값을 모두 합한 값
 → 최소 비용 생성 트리(Minimum Spanning Tree, MST)는 최소한의 비용만을 가짐

트리에 대한 대표적인 알고리즘은 다음과 같다.

프림의 알고리즘: 주어진 가중 그래프 G = (V, E)에 V = {1, 2, …, n}이라고 하자.
     ⑴ 노드의 집합 U를 1로 시작한다.
     ⑵ u ∈ U, v ∈ V - U일 때 U와 V를 연결하는 가장 짧은 연결선인 (u, v)를 찾아서 v를 U에 포함시킨다. 이때 (u, v)는 사이클을 형성하지 않아야 한다. 
     ⑶ ⑵의 과정을 U = V가 될 때까지 반복한다.

크루스칼의 알고리즘: 주어진 가중 그래프 G = (V, E)에 V = {1, 2, …, n}이라고 하고 T를 연결선의 집합이라고 하자.
     ⑴ T를 ∅으로 놓는다. 
     ⑵ 연결선의 집합 E를 비용이 적은 순서로 정렬한다.
     ⑶ 가장 최솟값을 가진 연결선 (u, v)를 차례로 찾아서 (u, v)가 사이클을 이루지 않으면 (u, v)를 T에 포함시킨다.
     ⑷ ⑶의 과정을 |T| = |V| - 1일 때까지 반복한다.
 → 연결선들을 비용이 적은 순서대로 나열하고, 연결선을 제거한 그래프에서 연결선의 비용이 적은 연결선의 순서대로 사이클이 생기지 않도록 나열하는 방법

 그래프(graph) G = (V, E)는 유한한 개수의 정점(vertex) 또는 노드(node)들의 집합인 V와 연결선(edge)이라 불리는 정점들의 쌍들의 집합인 E로 이루어진다.

 정점(v ∈ V): 그래프의 구성 요소

 → 차수(d(v)): 정점 v에 인접한 연결선들의 개수

 연결선(e ∈ E)/아크(arc): 정점들의 쌍으로 이루어지며, 정점들을 연결하는 선 

 → 경로(path): 정점들의 열 v1, v2, v3, ..., vk에서 인접한 정점들 사이의 연결선, 길이(개수)는 (k - 1)       

      ⑴ 단순 경로: 경로가 같은 연결선을 두 번포함하지 않는 경로       

      ⑵ 기본 경로: 어떤 정점들도 두 번 만나지 않는 경로

 → 사이클/순회(cycle, circuit): v1 = vk (k ≠ 1)인 경로

       ⑴ 단순 사이클: 같은 연결선을 반복하여 방문하지 않는 사이클

       ⑵ 기본 사이클: 시작점을 제외한 어떠한 정점도 반복하여  방문하지 않는 사이클

 그래프의 기본 개념은 다음과 같이 정리할 수 있다. 방향 그래프(directed graph) 혹은 다이그래프(digraph)는 G = (V, E)로 표시되는데, 이는 이전의 정리한 그래프의 정의와 대부분 유사하나, 이때 E는 정점들의 순서화된 쌍인 아크의 집합이 된다. 정점 v에서 w로 가는 아크는 v → w처럼 화살표를 통하여 표시한다.

 이어서 단순 그래프와 멀티 그래프를 정리하면, 단순 그래프(simple graph)는 한 쌍의 정점 사이의 연결선이 하나로 이루어진 그래프로 자기 자신으로의 연결선이 존재하지 않는다. 반면 멀티 그래프(multi graph)는 단순 그래프를 확장한 것으로, 한 쌍의 정점 사이 연결선 개수의 제한이 없는 일반적인 그래프를 말한다.

 이러한 그래프를 표현할 때, 인접 행렬(Adjacency Matrix)과 인접 리스트(Adjacency List)로 표현할 수 있다. 이 방법들은 C언어로 그래프를 구현할 때 유용하게 쓰인다. 그래프 G = (V, E), 정점 개수 n개라고 한다면 인접 행렬은 n x n 정사각형 행렬로 표현되며, 행(i)과 열(j)은 각각 정점 i와 j를 의미한다. 두 정점이 연결되어 있다면 1이고, 아니라면 0의 값을 가진다. 인접 리스트는 각 정점마다 연결된 정점들의 리스트를 저장하는 방식으로, 각각의 정점에 대해 포인터를 주고, 그 점으로부터 연결된 정점들을 차례대로 연결 리스트로  표시한다. 

 우리는 특수 형태의 그래프 역시 정리해 볼 수 있다.

 오일러 경로(Eulerian path): 그래프에서 각 연결선을 단 한 번씩만 통과하는 경로

 → 오일러 순회: 각 그래프에서 정점은 여러번 지날 수 있으나, 각 연결선을 단 한 번씩만 통과하는 순회

 → 어떤 그래프 G가 오일러 경로를 가지기 위한 필요충분조건은 G가 연결 그래프이고, 홀수 차수의 개수가 0이거나 2여야 함. 혹은 모든 정점들이 짝수 개의 차수를 가지는 경우. 후자의 경우 한붓그리기가 가능.

 해밀턴 경로(Hamiltonian path): 그래프에서 모든 정점을 오직 한 번씩만 지나지만, 시작점으로 돌아오지 않는 경로 → 해밀턴 순회: 그래프에서 모든 정점들을 오직 한 번씩만 지나는 순회 → 정점이 끊기지 않고 사이클을 만들 수 있는 구조이면 해밀턴 회로가 가능

 완전 그래프(Complete graph): 각 정점이 다른 모든 정점들과 연결되는 그래프로, n개의 정점으로 구성된 완전 그래프는 Kₙ로 표기

 → 정규 그래프: 그래프 G = (V, E)의 모든 정점의 차수가 k이면 G는 k차 정규 그래프

 이분 그래프(bipartite graph): 그래프 G가 두 부분 집합 X와 Y = V - X로 나누어져 각 연결선이 X 내의 정점과 Y 내의 정점의 쌍으로 연결된 그래프 → 모든 X, Y 내의 정점들 사이 연결선이 존재하면 완전 이분 그래프

 평면 그래프: 평면상의 어떠한 연결선들도 서로 교차할 수 없도록 그려진 하나의 그래프

 증명(proof)이란 논리적 법칙을 이용하여 주어진 가정으로부터 결론을 유도해내는 추론의 한 방법이다. 또한, 어떠한 명제나 논증이 적절하고 타당한지를 입증하는 작업이기도 하다. 이러한 증명의 단계적 접근 방법은 이러하다. 아이디어 스케치 → 방법론 제시 → 입증 및 증명

 수학이나 공학에서 새로운 결과를 얻는 두 가지 중요한 방법론은 다음과 같다.

연역법(deduction): 주어진 사실들과 공리들에 입각하여 추론을 통해 새로운 사실을 도출하는 것 (논리적 필연성)

귀납법(induction): 관찰과 실험에 기반한 가설을 귀납 추론을 통해 일반적인 규칙 입증 (경험적 일반화)

1. 수학적 귀납법

(Mathematical induction)

모든 정수 n에 대해 어떤 명제 p(n)이 주어졌을 경우 p(n)이 n ≥ 1인 모든 정수에 대해

참이라는 것을 증명하기 위한 방법은 다음 순서를 따른다.

① (기초 단계) p(1)이 참임을 보임

② (귀납 가정) p(n)이 참이라 가정

③ (귀납 단계) 귀납 가정에 입각하여 p(n+1)이 참임을 보임

2. 모순 증명법

(Proof by Contradiction)

결론의 부정을 가정하여 모순이 발생함을 보이고, 결론이 참임을 증명 

모순은 논리적 불가능 상태

ex) 2^1/2이 무리수 → 2^1/2이 유리수라고 가정

3. 직접 증명법

(Direct proof)

전제를 참으로 놓고 논리적 연역을 통해 결론을 입증

'p → q' 그대로 증명

ex) 짝수의 제곱은 짝수 n=2k → n^2=4k^2=2(2k^2)

4. 대우 증명법

(Contraposition proof)

'~q → ~p' 증명대우는 논리적 동치 p → q ≡ ~q → ~p

ex) 3n+2가 홀수면 n은 홀수 → n이 짝수면 3n+2는 짝수

5. 존재 증명법

(Existence proof)

존재를 직접 제시하거나, 간접적으로 증명

∃x ∈ S, P(x) 형태의 명제가 참임을 보임

ex) 짝수 소수가 존재 → '2' 존재 제시

6. 반례 증명법

(Proof by Counter-example)

명제 ∀x P(x)가 거짓임을 보이기 위해 하나의 반례 제시

∀ 반박 시 하나의 반례면 충분

ex) 모든 소수는 홀수이다 → '2' 반례 제시

7. 필요충분조건 증명법

(if and only if proof)

① 필요조건

Q가 참이려면 P가 반드시 참이어야 함

(Q → P)

'Q이면 P' 증명

② 충분조건

p가 참이면 Q도 참임

(P → Q)

'P이면 Q' 증명

③ 필요충분조건

양방향 모두 참

(P ↔ Q)

두 방향의 증명 각각 수행