엔지니어가 되고 싶은 공돌이

12. 그래프의 정의와 종류(Graph) 본문

Mathematics/Discrete Mathematics

12. 그래프의 정의와 종류(Graph)

Geca 2024. 5. 14. 15:47

 

12. 1. 그래프의 정의(Definition of Graph)

 

- 그래프(Graph: G=(V, E)): 꼭짓점(Node)의 집합 V와 서로 다른 꼭짓점을 연결하는 모서리(Edge)의 집합 E로 구성된 구조.

 

- G = (V, E) 에서 Node u, v를 연결한 Edge e가 있을 때, u와 v는 서로 인접(Adjacent)하고, Edge e는 Node u, v에 근접(Incident)한다고 말한다.

 

- Loop: edge가 하나의 node에만 연결되어 있을 때.

 

 

- 다중 그래프(Multi Graph): Graph에서 동일한 Node사이에 두 개 이상의 Edge가 있는 그래프.

 

- 방향 그래프(Directed Graph, G = <V, E>): Edge에 화살표(방향)가 있는 그래프.

 

- 가중치 그래프(Weighted Graph): Graph에서 각 Edge에 숫자(가중치)가 부여된 그래프.

 

- 차수(Degree, d(v)): 하나의 Node에 연결된 Edge의 개수.

 

- Odd Degree: 차수가 홀수인 Node / Even Degree: 차수가 짝수인 Node.

 

- Directed Graph에서 Node v를 시작으로 하는 화살표의 수를 Out-Degree(out-d(v)), Node v를 끝으로 하는 화살표의 수를 In-Degree(in-d(v)) 라 부른다.

 

- Graph에서 모든 Node의 Degree의 합은 Edge의 2배이다.

 

  Graph에서 Degree가 홀수인 Node의 수는 짝수이다.

 


 

12. 2. 그래프의 종류(Types of Graphs)

 

- 부분 그래프(Subgraph): Graph G = (V, E)가 있을 때, V’ ⊆ V이고, E’ ⊆ E인 그래프 G’ = (V’, E’).

 

- 부분 신장 그래프(Spanning Graph): Graph G = (V, E)가 있을 때, V’ = V이고, E’ ⊆ E인 그래프 G’ = (V’, E’).

 

- 동형 그래프(Isomorphic Graph): Graph 모양은 달라도 V와 E의 집합이 서로 같은 그래프.

 

 

- 평면 그래프(Planer Graph): Graph를 평면에 그릴 때, Node가 아닌 곳에서 어떠한 Edge도 교차하지 않는 그래프.

 

- 평면 그래프 오일러 공식(Euler’s Formula): vertex number – edge number – Area number = 2.

Area는 Graph에 의해서 평면에서 나누어지는 구별된 영역을 의미한다.

 

 

- 연결 그래프(Connected Graph): Graph의 어떠한 Node를 선택해도 임의의 어떠한 Node로 갈 수 있는 그래프.

 

- 완전 그래프(Complete Graph, Kn): Graph의 모든 n개의 Node 사이에 Edge 가 있는 그래프.

 

- 정규 그래프(Regular Graph, k-Regular): Graph의 모든 Node의 Degree가 k로 같은 그래프.

 

 

- 이분 그래프(Bipartite Graph): Graph에서 Node가 두 개의 집합 N1, N2 으로 분리되고, 그래프의 모든 Edge가 N1의 한 꼭짓점에서 N2의 임의의 Node로 연결되는 그래프.

 

- 완전 이분 그래프(Complete Bipartite Graph): Graph에서 Node가 두 개의 집합 N1, N2 으로 분리되고, 그래프의 모든 Edge가 N1의 한 꼭짓점에서 N2의 모든 Node로 연결되는 그래프.

 

- 같은 집합 내의 Node 간에는 Edge가 존재하지 않는다.

 


Comments