방향그래프 , 강한결합요소(순환하는 부분 찾기)

 방향그래프 , 깊이우선탐색 Warshall 알고리즘

강한결합요소 찾기 문제

위상정렬/ 역위상정렬

AOE Network

Network 방향그래프 이면서 간선의 가중치가 있는 그래프

---

방향그래프 : 간선에 방향성이 한방향으로만 연결되어 있는 그래프

(Tip : 무방향그래프의 간선은 양방향 간선이다)

내차수(In-degree) : 정점으로 들어오는 간선수

외차수(Out-degree) 정점에서 나가는 간선수

---

도달가능성(Reachability)

한 정점에서 다른 모든 정점을 방문할 수 있는 건 아니다(방향성이 있기 때문)

(깊이우선 탐색 : 모든 노드를 탐색 하는 방법)

그래서 깊이우선 탐색으로 시작점을 줄 수 있는 깊이우선 탐색으로 조금 변경한 후

해당 노드에서 인접노드를 스택에 넣고, 스택에 넣었던 노드중 하나를 꺼내어서 꺼낸 노드를 방문하고

이 노드의 인접 노드를 다시 스택에 넣고 또다시 방문하고를 바복하면서

방향성으로 갈 수 있는 노드를 따라 가다보면 시작하려고 했던 노드에서의 방향성이 어디까지 접근 할 수 있는지

도달가능범위를 알 수 있다

---

Transitive closure( 이행적 폐쇄 )

어떤 정점 A 에서 C 로 가는 방향에 대해서 직접 경로는 없지만, 우회 경로가 있을때 A->C 로 의 간선을 연결한 그래프( 방향으로 갈 수 있을 때 )

---

Warshall 알고리즘

그리고 A->A 도 가능하기에 배열 테이블의 대각선 값은 1 이 된다

A->B 와 B-C 를 만족하는 경로가 있으면 A->C로 가는 경로도 존재한다

그래서 A->C 로 접근 가능하다를 구현한 것 => 배열 테이블에서 A->C 로 가는 값을 세팅해준다

A->B 로 가는 값이 1로 세팅이 되어 있고 B 에서 C 로 가는 값에도 1 로 세팅 되어 있으면

A에서 C 로 가는 값을 1 로 세팅해준다( 접근 가능경로로 만든다 ) => warshall

그다음 반복...

위에서 A->C 로 가는 값이 1 이므로

C->F 로 가는 값이 1 이고 F->D 로 가는 값 또한 1 이라면 C->D 로 가는 값을 1 로 세팅해준다

[C++ 알고리즘 참고]

---

[강한결합요소]

: 정점 A 에서 B로 가는 방향성 경로도 존재하고 B 에서 A로가는 방향성경로도 존재

( 사이클로 이루어지고 한쪽 방향으로 도는 경우를 말함 )

- 강한결합요소는 정점 하나를 제거해도 연결은 유지된다

( 강한결합요소의 경우 정점 하나를 제거해도 나머지 노드들끼리는 연결되어 있다는 것 )

중요한 부분에서 는 강현 결합요소로 연결해주면 좋다

VS

이중연결(biconnectivity) : 한쪽 말고도 다른쪽으로도 연결 되어 있는 구조

[강한결합요소 찾기]

왼쪽 트리의 간선에 비용을 매겨서 깊이우선 탐색으로 모든 노드 방향에 대해 탐색 하는 경로를 얻은 후

오른 쪽에는 깊우우선 탐색으로 얻은 것을 먼저 그린후( 빨간선 제외)

모든 노드를 연결하는 경로 외의 선(오른쪽 그림에서 붉은 선) 에 대해서

왼쪽 방향대로 연결해주었을때 오른쪽 그림의 가장 하위 정점에서 자기자신 을 가르키게 되면 그것이 강한결합이 된다

(각 노드에서 빨간색을 타고 올라갔을때 1의 노드(비트리간선으로 자기자신)가 다시 나오면 강한결합이 된다)

오른쪽 그림에는 두가지의 강한결합을 보여주고 있다

빨간색선 : 난트리엣지( = 방문하지 안은 엣지)

파랑색 : 트리엣지 ( = 방문한 엣지)

1. A->D->F->E ->A , A 로 시작해서 가장 하위로 갔을때 그것이 자기자신을 가르키는 경우를 강한 요소라 한다

2. G->J->I ->G