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: 한 쌍의 vertex 사이에 많아도 하나의 edge로 이루어진 그래프
- multi graph: 한 쌍의 vertex 상이에 여러 개의 edge가 존재할 수 있는 그래프
- connected graph: graph의 모든 vertex들이 연결되어 있는 graph
- strongly connected graph: directed graph에서 v1과 v2가 연결되어 있을 때
v1 -> v2, v2 -> v1의 경로들이 존재하는 graph
- connectivity component: graph에서 모든 vertex들이 연결되어 있는 부분을 말 함.
- connectivity number: graph의 connectivity component의 개수
Eulerian path(오일러 경로)
"어떤 G가 오일러 경로를 가지기 위한 필요충분조건은 G가 연결 그래프이고, 홀수 차수의 개수가 0 또는 2인 경우"
오일러 경로의 특징은 "G의 각 edge를 단 한 번씩만 통과하는 경로"
오일러 순회의 특징은 "G에서 vertex는 여러 번 지날 수 있지만 각 edge를 단 한번 씩만 통과하는 순회를 말한다."
Hamiltonian path & circuit(해밀턴 경로 & 회로)
해밀턴 경로: "G에서 모든 vertex를 오직 한 번씩만 지나지만 시작점으로 돌아오지 않는 경로"
해밀턴 회로: "G에서 모든 vertex를 오직 한 번씩만 지나는 순회를 말함."
순회는 무조건 다시 돌아오는 것임을 명심