티스토리 뷰
그래프의 정의
- 그래프 G는 정점 V(Vertex)와 간선 E(Edge)의 두 집합으로 이루어짐
- 통신망(Network), 교통망, 이항관계, 연립방정식, 유기화학 구조식, 무향선분 해법 등에 운용됨
- Tree는 사이클이 없는 Graph임
용어 정리
- Loop : 한 정점에서 그 자신에 이어지는 간선 Loop
- 차수(Degree)
＊ 무방향 그래프 : 한 정점에 연결된 간선의 수
＊ 방향 그래프
- 진입 차수(Indegree) : 한 정점에 도착하는 방향 간선의 수
- 진출 차수(Outdegree) : 한 정점에서 출발하는 방향 간선의 수
- 차수(Degree) = 진입 차수 + 진출 차수
- 예 )
＊ G1 그래프에서 Degree(1) = 3
＊ G3 그래프에서 Indegree(2) = 1
Outdegree(2) = 2
Degree(2) = 3
- 경로(Path)
＊ 임의의 정점에서 다르정점에 이르는 길
- 경로 길이(Path Length) : 경로상에 있는 간선들의 수
- 단순 경로(Simple Path) : 한 경로상에 있는 모든 간선이 서로 다를 때의 경로, 즉 같은 간선을 두 번 이상 지나지 않는 경로
- 기본 경로(Basic Path) : 한 경로상에 있는 모든 정점이 유일할 떄의 경로, 즉 같은 정점을 두 번 이상 지나지 않는 경로
- 사이클(Cycle) : 같은 정점에서 시작과 끝이 이루어지는 경로
- 최대 사이클 : 사이클을 이루는 경로 중 최대 경로 길이
- 연결 요소(Connected Component)
＊ 무방향 그래프에서 최대 연결 서브 그래프
＊ 예) G1의 연결 요소는 G1 자신이다
- 강력 연결 요소(Strongly Connected Component)
＊ 방향 그래프에서 두 정점 사이의 간선이 양방향으로 서로 강력하게 연결되어 있는 요소, 즉 두 정점 사이에 방향 사이클이 이루어지는 요소
★ 인접행렬을 이용한 그래프의 표현 방법
- 방향 그래프에서 ViVj 관계를 나타내는 행렬의 원소를 Pij라 할 때, 방향 간선이 있으면 행렬의 Pij = 1, 없으면 Pij = 0
- 예 )
- 무방향 그래프에서 Vi와 Vj가 서로 인접하면 Pij = 1, 인접하지 않으면 Pij = 0
- 예 )
특수 그래프
- 최소 비용 신장 트리(MST, Minimum-Cost Spanning Tree)
＊ 최소 비용 신장 트리는 가중치(각 간선에 기술된 값)가 가장 작은 간선들을 사이클을 이루지 않도록 연결시켜 만든 그래프임
- 간선 작업 네트워크(AOE Network)
＊ 간선 작업 네트워크는 프로젝트 해결을 위해 수행되는 작업 순서를 나타내는 방향 그래프임
＊ 간선은 작업과 작업시간을 나타내고, 정점이 공정(작업의 완료)을 나타냄
＊ 임계 영역(Critical Path) : 최장 길이를 갖는 경로1
- 각 작업은 병행수행될 수 있기 때문에 프로젝트를 완료하기 위한 경로 중에서 작업시간이 가장 긴 경로 [본문으로]