3) 그래프, 트리

그래프: 정점들의 집합 V(v_1,v_2,v_3...,v_n) 과 간선들의 집합 E={e_1,e_2,e_3....,e_m}으로 이루어진 구조.

 

간선: 각 간선은 집합 V에 있는 정점들의 쌍

$$e_i = (v_j,v_k)$$

간선 e_i는 v_j로부터 시작하고 v_k에 도착하는 간선이 된다. v_j를 기준으로 하면 진출간선이라 하고, v_k를 기준으로 하면 진입간선이라 한다.

 

유향 그래프: 각 간선에 방향을 지정한 그래프

 

라벨 그래프: 각 정점이나 간선에 라벨을 지정한 그래프. 라벨은 특별한 이름이나 정보일 수 있다.

 

정점이 {v_1,v_2,v_3}이고 간선들의 집합이 {(v_1,v_3),(v_3,v_1),(v_3,v_2),(v_3,v_3)}인 그래프에서 간선들은 v_i로부터 v_n으로의  "보행" 이라 불리며, 보행의 "길이"는 보행의 시작정점부터 도착정점까지 지나게 되는 간선들의 수다.

 

단순경로: 어느 정점도 중복하여 지나지 않는 경로

사이클: 어느 간선도 중복하여 지나지 않고, 자기 자신에게로 돌아오는 경로

단순 사이클: 어느 정점도 중복하여 지나지 않고, 자기 자신에게로 돌아오는 경로

루프: 한 정점에서 자기자신으로의 진입간선

 

트리: 그래프의 한 종류. 사이클을 갖지 않고, 루트라 불리는 특별한 하나의 정점을 가지는 유향 그래프.

리프: 트리의 정점

부모, 자식: v_i에서 v_j로 가는 간선이 있을때, v_i를 부모, v_j를 자식이라 한다.

레벨: 루트부터 해당 노드의 간선의 개수

높이: 루트부터 최고레벨까지의 간선의 개수

 

증명기법

 

귀납법: 몇개의 특정한 사례가 참이라는 사실로부터 여러 문장이 참임을 추론하는 기법

귀류법: 어떤 문장 P가 거짓이라 가정하고, 그 가정으로 인해 어떤 사실들이 유도되는지 보고, 유도 된것이 거짓이라면 P가 참이어야 한다거 결론 짓는 기법