그래프 (Graph)
정의 G=(V, E) [ V = 공집합이 아닌 정점(vertex)들의 유한집합 ] [ E = 정점들의 쌍인 간선(edge)들의 집합 ] 무방향 그래프 (Undirected Graph) 방향 그래프 (Directed Graph) V(G1) = {0, 1, 2, 3} E(G1) = {(0,1), (0,2), (0,3), (1,2), (1,3), 2,3)} V(G3) = {0, 1, 2} E(G3) = {, , } = E(G)의 간선 (u, v)에 대해 u와 v는 인접한다(adjacent)라고 하며 간선 (u, v)는 정점 u와 v에 부속된다(incident)고 한다. 완전 그래프 (Complete Graph) n개의 정점을 갖는 무방향 그래프 간선 최대수 = n(n-1)/2 부분 그래프 (Sub Graph)..
트리 (Tree)
기본 용어 Tree 정의 : node로 이루어진 유한집합으로 root node와 나머지 노드 (T_1, T_2, ..., T_n)으로 분리. 이때 T_i는 각각 하나의 tree (sub tree 혹은 부분 tree)라 함 node의 차수(degree) 해당 node의 sub tree 수 tree의 차수 tree에 포함된 node들 중 최대 차수 리프(leaf) 또는 단말노드(terminal) 차수가 0인 node ex) K, L, F, G, M, I, J 비단말노드(non-terminal) 차수가 0이 아닌 node ex) A, B, C, D, E, H 레벨(level) root level이 1일 때 부모-자식은 1 level씩 증가 tree 깊이(depth) 또는 높이(height) tree에 속한 n..
