그래프 이론과 기초 개념 정리

그래프(Graph): Vertex와 edge로 구성된 네트워크 구조.

발생(Incidence): edge가 Vertex에 연결되는 방법을 나타냅니다.

 

인접성(Adjacency): 두 vertex가 edge로 직접 연결되어 있는 상태를 나타냅니다.

 

워크(Walk): vertex와  edge를 번갈아가며 나열한 시퀀스로, 중복된 vertex와 edge가 포함될 수 있습니다.

 

트레일(Trail): 중복된 edge가 없는 Walk로, 정점 간에 경로를 따라 이동합니다.

 

회로(Circuit): 시작과 끝 vertex가 같으며, 중복된 edge가 없는 닫힌 경로입니다.

 

패스(Path): 중복된 vertex를 포함하지 않는 Walk로, vertex를 순서대로 이동합니다.

 

사이클(Cycle): 시작과 끝 vertex가 같으며, 중복된 edge가 없는 닫힌 경로로, 최소한 한개의 edge를 포함합니다.

 

열린(Open) / 닫힌(Closed): Walk나 경로가 시작과 끝 vertex가 같으면 닫힌(Closed)이고, 다르면 열린(Open) 경로입니다.

 

연결된 그래프(Connected Graph): 그래프 내의 모든 vertex 사이에 경로가 존재하는 그래프입니다.

 

컴포넌트(Components): 그래프 내에서 최대로 연결된 부분들을 의미합니다.

 

강하게 연결된(Strongly connected): 모든 vertex 쌍 간에 양방향 경로가 존재하는 경우를 나타냅니다.

 

단방향으로 연결된(Unilaterally connected): 모든 vertex 쌍 간에 최소한 하나의 방향 경로가 존재하는 경우를 나타냅니다.

 

약하게 연결된(Weakly connected): 방향 그래프에서 연관된 그래프(방향을 무시한 그래프)가 연결된 경우를 나타냅니다.

 

다중그래프(Multigraph): 동일한 두 vertex 사이에 여러 개의 edge가 있을 수 있는 그래프입니다.

 

다중도(Multiplicity): Multigraph에서 동일한 edge가 여러 번 방복되는 것을 나타냅니다.

 

방향 다중그래프(Directed multigraph): 방향성을 가지며 동일한 두 vertex 사이에 여러 개의 방향 edge가 있을 수 있는 그래프입니다.