Graph & Tree의 정의
이번 Posting에서는 Graph와 Tree에 대해서 정리를 해볼 생각입니다. 1. Graph "G는 V(Vertex, 노드) set과 E(엣지) set으로 구성되는 구조" 자 정의는 엄청 간단합니다 !! 뭐 여러가지 용어들(path, cycle, adjacent, incident, simple path, elementary path, loop, circuit, simple cycle, elementary cycle, undirected graph, directed graph, degree, simple graph, multi graph, connected graph, strongly connected graph, connectivity component)이 있지만.... 적다보니 많네요 ;; 한 번씩 정리해보고 가죠. path: vertex들의 sequence. cycle: v1 = vk(k != 1)인 점이 존재 length: path or cycle을 구성하는 변의 수 adjacent: edge하나를 두고 vertex 2개가 서로 연결되어있는 상황 incident: edge와 vertex가 연결되어 있을 때 둘은 근접 함. simple path: 같은 edge를 2개 이상 포함하지 않는 path elementary path: 어떤 vertex들도 두 번 만나지 않는 경로 loop: 근접하는 vertex가 같은 edge circuit: (= cycle) simple cycle: 같은 edge를 반복하여 방문하지 않는 cycle elementary cycle: start point를 제외한 어떠한 vertex도 반복하여 방문하지 않는 cycle undirected graph: 방향이 없는 graph directed graph: 방향성이 있음. degree: vertex에 연결된 edge의 총 합 simple graph: 한 쌍...