그래프

그래프의 정의

• 그래프 G는 정점 V(Vertax)와 간선 E(Edge)의 두 집합으로 이루어짐
• 간선의 방향성 유무에 따라 방향 그래프와 무방향 그래프로 구분됨
• 통신망, 교통망, 이항관계, 연립방정식, 유기화학 구조식, 무향성분 해법 등에 이용
• Tree는 사이클이 없는 Graph입니다.

---

용어 정리

Loop - 한 정점에서 그 자신에 이어지는 간선 Loop

 

차수

• 무방향 그래프 : 한 정점에 연결된 간선의 수
• 방향 그래프

- 진입 차수(Indegree) : 한 정점에 도착하는 방향 간선의 수

- 진출 차수(Outdegree) : 한 정점에서 출발하는 방향 간선의 수

- 차수 = 진입차수 + 진출 차수

 

경로(Path)- 임의의 정점에서 다른 정점에 이르는 길

• 경로 길이 : 경로상에 있는 간선들의 수
• 단순 경로 : 한 경로상에 있는 모든 간선이 서로 다를 때의 경로 같은 간선을 한번 지납니다.
• 기본 경로 : 한 경로상에 있는 모든 정점에 유일할 때의 경로
• 사이클 : 같은 정점에서 시작과 끝이 이루어지는 경로
• 최대 사이클 : 사이클을 이루는 경로중 최대 경로 길이

연결 요소 - 무방향 글프에서의 최대 연결 서브그래프

 

강력 연결 요소 - 방향그래프에서 두 정점 사이의 간선이 양방향으로 서로 강력하게 연결되어 있는 요소, 즉 두 정점 사이에 방향 사이클이 이루어짐

---

특수 그래프

최소 비용 신장 트리(MST, Minimum-Cost Spanning Tree)

 

최소 비용 신장 트리는 가중치(각 간선에 기술된 값)가 가장 작은 간선들을 사이클을 이루지 않도록 연결시켜 만든 그래프입니다.

 

간선 작업 네트워크(AOE Network)

• 간선 작업 네트워크는 프로젝트 해결을 위해 수행되는 작업 순서를 나타내는 방향 그래프 입니다.
• 간선은 작업과 작업시간을 나타내고, 정점이 공정을 나타냅니다.
• 임계 경로(Critical Path) : 최장 길이를 갖는 경로