엔지니어가 되고 싶은 공돌이
12. 그래프의 정의와 종류(Graph) 본문
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가 존재하지 않는다.
'Mathematics > Discrete Mathematics' 카테고리의 다른 글
14. 트리의 정의(Definition of Tree) (0) | 2024.05.16 |
---|---|
13. 그래프의 표현과 활용(Expression and Use of Graphs) (0) | 2024.05.15 |
11. 함수(Function) (0) | 2024.05.12 |
10. 관계의 폐포, 동치관계(Closure of Relation & Equivalence Relation) (0) | 2024.05.11 |
09. 관계의 성질, 합성관계(Properties of Relations & Composition Relation) (0) | 2024.05.10 |