[이산수학] 방향그래프, 그래프 탐색과 구현

<< 이산수학 7주차 >>

11. 방향그래프 
12. 강한연결요소 
13. 비순환그래프 
14. 그래프탐색 
15. 그래프구현

---------------------------------------------------------------------------------

⑪ 방향그래프 
: 간선의 끝에 방향을 추가

G = (V, E)
V : 노드(nodes)라고 부른다.
E : 아크(arcs)라고 부른다. //★관계를 순서쌍으로 표현한다.★

예제)
G = (V,E)
V = {1,2,3,4}
E = { (1,2), (2,1), (2,5), (3,1), (3,4), (4,2), (5,4), (5,5) }

차수 : 정점에 연결된 간선의 수
 //사람으로 따지면 인기인 <->고립된 사람으로 취급함

deg = indeg+outdeg
- indeg(v)   //v로 들어오는 진입 차수
- outdeg(v)   //v로부터 나가는 진입차수
간선의 개수 = indeg = outdeg

정점 구분
1. 출발점 indeg(v)=0
2. 도착점 outdeg(v)=0
3. 고립점 indeg(v)=0 && outdeg(v)=0
4. 환승점 otherwise //출발이면서 동시에 도착 정점

점정 구분 예시

⑫ 강한연결요소(SCC)
: Strongly Connected Component
"모든 컴퓨터이 다른 컴퓨터로 메일을 보낼 수 있는지?"
두 개의 정점이 u에서 v까지 가는 경로가 있다면, v에서 u로 가는 경로가 있다. >> 강한 연결

SCC는 어디에 활용되는가? "일반통행 설계" >> SCC개수 1개


⑬ 비순환그래프
작업일정을 나타내는 그래프는 순환이 존재해서는 안된다.
"DAG" //Directed Acycle Graph

사이클 존재 여부 판정 방법
1. Consistent Labeling 아이디어
그래프에다가 숫자를 배열하여 시작점의 수는 끝점보다 작다.
 >> (vi, vj)∈E -> i
작업 일정 계획에 활용된다. (ex. 건축 일정 계획)
이전 작업을 끝내야 다음 과정을 진행할 수 있다.

다양한 consistent labeling이 가능하다. 

// 알고리즘
cycle detection( ) :
compute A(v)  // 이전의 정접들의 집합 초기화
while unabled vertices v // 정점들이 남아있을 때까지
label+=1
A(v)=공집합
for unabled vertices u
A(u) = A(u)-{v}
if 남아있는 정점들이 있다면, 사이클이 존재하는 것임.

(관계 부분순서 -> 전체 순서)와 비슷한 개념

최소 완료 시간은?
1. 그래프모델링
2. 사이클 존재 여부 확인
3. 최소 완료 시간 계산

최소로 완료 되는데 걸리는 시간 = "임계 경로(critical path)"   // 다른 경로보다 중요함.
임계 경로에서 지체가 되면, 전체 최소 완료 시간에 영향을 끼친다.

(작업일정표)
작업 ID | 시간 | 선행작업 작성
 // 그 후에 -> 방향 그래프 -> 순환여부 -> DAG, 임계 경로 찾기
 // MS프로젝트(도구) 또는 open project



⑭ 그래프탐색
: 주어진 그래프에서 원하는 정점 찾기

- 너비 우선 탐색(BFS) : 인접한 정점들을 차례로 탐색
    level by level
    큐 사용
- 깊이 우선 탐색(DFS) : 먼저 만난 정점들을 먼저 탐색
    스택 사용

컴퓨터에 저장된 순서대로 진행 >> BFS
: v1 -> v2 -> v5 -> v6 -> v3 -> v7 -> v4
컴퓨터에 저장된 순서대로 초이스 >> DFA //★backtracking★
: v1 -> v2 -> v3 -> v4 -> v7 -> v6 -> v5  // v5에서 branch하나 추가


//DFS 알고리즘
procedure DFS(G) :
T = v1으로만 구성된 트리
visit(v1) //v1에 인접된 각각의 정점에 대해서 재귀

procedure visit(v) :
for 트리에 없는 인접된 정점들에 대해서
   정점 v2를 더해라
   visit(v2) //재귀


// BFS 알고리즘
procedure BFS(G) :
T = v1으로 구성된 트리
L = empty list(큐)
L <- v1

while L이 empty가 아닐 때까지
   remove v1 (from L) //v1을 끄집어낸다.
   for v1에 인접한 정점 v2에 대해서
if v2가 트리에 없다면
L에 넣음
T에도 넣음



⑮ 그래프구현
다양한 학과에서 이산수학을 수강하는데 컴공에서는 문제풀이 단계를 위주로 한다.
주어진 문제에 대한 -> 모델링을 통해 -> 추상 모델 그래프를 -> 알고리즘을 만들고 -> 컴퓨터 프로그램으로 만드는 과정을 가진다. 

그래프 프로그램
- 연결 요소의 수 찾기
- 그래프 색칠에 요구되는 최소 색상 수 찾기(Greedy Algorithm)
- 최소 비용의 헤밀턴 경로 찾기(TSP -> Nearest Neighbor Algorithm)
- 너비우선탐색으로 원하는 정점 찾기(BFS)
- 깊이우선탐색으로 원하는 정점 찾기(DFS)
- 강결합 연결 요소 찾기
- 사이클 존재여부 찾기(Topological sorting)