A Quick Review of Cut Vertex

  • Root of a DFS tree is a cut vertex iff it has more than one child
  • Non-root node t?
  • For each t compute l(t), which is the minimum of
    • pre(t)
    • Min of pre(s) where (t, s) is a back edge
    • Min of pre(u) for all children of t
    • t is a cut vertex iff exists a child u of t such that l(u) >= pre(t)

Time Complexity

위의 알고리즘을 그대로 가져와보자.

  • Root of a DFS tree is a cut vertex iff it has more than one child –> O(m+n)
  • Non-root node t? –> O(1)
  • For each t compute l(t), which is the minimum of –> O(m+n)
    • pre(t) –> O(1)
    • Min of pre(s) where (t, s) is a back edge –> O(degree(t))
    • Min of pre(u) for all children of t –> O(degree(t)) (child가 미리 계산돼 있다고 가정할 경우)
    • t is a cut vertex iff exists a child u of t such that l(u) >= pre(t)

따라서 전체 시간 복잡도는 O(m+n)이다.

그럼 이제 Cut Vertex와 연관된 문제 두 개를 보자.

Cut Edge

그래프의 한 엣지가 사라질 때 그래프가 끊어진다면, 그 엣지를 Cut Edge라 정의한다. Cut Edge를 찾는 알고리즘을 Cut Vertex를 찾는 알고리즘과 거의 동일하다.

p1

모든 엣지마다 중간에 빨간 노드를 넣은 후 DFS를 수행해 Cut Vertex를 찾는다.

그리고 찾은 Cut Vertex 중 빨간 노드가 있는지 본다. 만약 빨간 노드들 중에 Cut Vertex가 있다면, 빨간 노드와 바로 연결된 엣지가 Cut Edge이다.

BCC

  • Biconnected Component
  • Parts of a graph separated by Cut Vertices
  • Two nodes in a BCC have completely different paths connecting them
  • The meaning of “separated” can be confusing

Cut Edge를 구하는 것이 더 쉽지만 Cut Vertex를 배우는 이유는 Cut Vertex가 더 의미가 크기 때문이다.

아래의 그래프를 보자.

p2

위 그래프에서는 Cut Edge가 존재하지 않는다. 다시 말해 엣지 하나를 제거해 그래프를 끊어낼 수 없다. 그러나 Cut Vertex는 존재한다.

BCC 기준으로 두 덩어리로 나누어질 수 있는데 왜냐하면 두 까만색 노드는 biconnected하지 않기 때문이다.

biconnected란, 한 노드에서 다른 노드를 연결하는 path가 여러 개가 있을 때 완전히 독립적인 path가 두 개 이상 존재하는 것을 의미한다. 즉 두 path 사이에는 공유하는 노드도 없고 공유하는 엣지도 없어야 한다.

p3

Cut Vertex가 존재한다는 것은, Cut Vertex 하나만 사라져도 연결이 끊긴 노드들이 생긴다는 것을 의미하므로 두 노드가 biconnected하지 않다는 것을 의미한다.

그래프 전체가 biconnected하다면 Cut Vertex가 존재하지 않는다. Cut Vertex가 있다면, 그래프의 일부는 biconnected할 수 있어도 전체가 biconnected하지는 않다.

다시 위의 그래프를 보면, 그래프 전체는 biconnected하지 않다. 왼쪽 까만 노드에서 오른쪽 까만 노드로 가는 path는 네 개가 있지만 이들이 모두 가운데 노드를 공유하기 때문이다. 그런데 왼쪽의 네 개의 노드만 보면 두 개의 독립적인 path가 존재하므로 biconnected graph이다. 마찬가지로 오른쪽 네 개의 노드만 보아도 biconnected하다. Cut Vertex는 여러 군데 포함될 수 있다..! 그래서 separated하다는 표현이 헷갈릴 수 있음.

Detecting BCC

  • Find Cut Vertices
  • Does not work: do DFS, stop at Cut Vertices
  • In Cut Vertex algorithm, each subtree can be marked as BCC

그러면 BCC인지 어떻게 확인할 수 있을까. DFS를 하다가 Cut Vertex에서 멈추면 되지 않을까? 그렇지는 않다. 아래 그래프에서 BCC는 네 개지만, 한 Cut Vertex에서 시작해 육각형을 따라 이동하면 다른 Cut Vertex에서 멈춰버리기 때문이다.

p4

다행히도 Cut Vertex 알고리즘으로 BCC를 만들 수 있다. DFS를 돌렸을 때 root의 child가 세 개이면 root는 cut vertex이고 세 명의 child를 각각 root로 하는 subtree로 나눠진다.

p5

그리고 한 subtree에서 root까지 올라오는 백엣지가 있으면 root는 그 BCC에 포함된다. 만약 백엣지가 존재한다면 subtree의 root, 즉 child를 포함하는 BCC에 root를 첨가해야 한다.

p6

root까지 올라오는 백엣지가 존재하지 않는 경우에는 상관이 없다.

p7

Topological Sort (위상 정렬)

  • DAG: Directed Acyclic Graph
  • Sort nodes so that all links are left to right
  • Is it always possible?
    • Impossible if there are cycles
    • Always possible if no cycle: proven by algorithm

DAG는 그래프 전체에 방향성을 부여한다. 옷을 입을 때 무엇을 먼저 입어야 한다 등 의존 관계가 있을 때 많이 사용된다. 먼저 해야 하는 것이 있는데 사이클이 존재하면 안 된다!

DAG로 문제를 풀기 위해서는 가장 먼저 topological sort(위상 정렬)를 해야 한다. 위상 정렬 자체가 성능을 개선하지는 않지만, 위상 정렬을 해주면 생각하기가 훨씬 편함. 사실 DAG에서 하는 알고리즘들의 상당수가 이미 위상 정렬의 개념을 포함하고 있다.

Definition: Sort nodes so that all links are left to right.

모든 링크가 왼쪽에서 오른쪽으로 가도록 노드를 정렬하는 것이다.

p8

위상 정렬이 항상 가능한 것은 아니다. cycle이 존재하는 경우에는 위상 정렬을 할 수 없다.

사이클이 존재하는 노드 네 개짜리 그래프를 한 줄로 정렬시켰다고 가정해보자.

p9

사이클이 존재하므로 임의의 노드에서 시작해 링크를 따라가보면 제자리로 돌아온다. 제자리로 돌아온다는 것은 정렬된 그래프에서 오른쪽에서 왼쪽으로 가는 링크가 존재한다는 것을 의미하고, 이는 위상정렬의 정의에 모순이다.

반면 사이클이 존재하지 않는 경우에는 언제나 위상 정렬을 할 수 있다. acyclic 그래프를 입력으로 주면 항상 위상 정렬을 해주는 알고리즘이 존재한다!

그럼 이제 그 알고리즘을 보자. 이 알고리즘은 관찰로부터 시작딘다.

Observation: There has to be at least one node with indegree==0.

증명: DAG에서 indegree가 0인 노드가 하나도 없다고 가정한다.

그러면 들어오는 링크(엣지)가 존재하고 그 링크를 거꾸로 따라가면 다른 노드에 가게 된다.

p10

근데 indegree==0인 노드가 하나도 없다 가정했으므로 다른 노드로 엣지를 거꾸로 따라 간다. 노드 개수는 n으로 fix돼 있는데, 이 과정이 멈출 수 없으므로 같은 노드를 두 번 이상 방문하는 경우가 발생한다. 즉 indegree가 0인 노드가 없으면 그래프 내에 사이클이 존재한다.

Algorithm

  • From DAG G, remove one node with indegree==0
  • The rest(G’) is still DAG
  • If you can topologically sort G’ then you can topologically sort G

  1. G’는 원래 그래프에서 노드 하나를 제거한 것이다. G 가 사이클이 존재하지 않는 그래프이므로 G에서 노드 하나를 제거한다고 해서 사이클이 생기지는 않는다.

  2. G’를 위상 정렬 할 수 있으면 G도 위상 정렬 할 수 있다. 이는 수학적 귀납법(재귀에서의 step)으로 증명할 수 있다.

G’을 위상 정렬한 결과가 다음과 같다고 해보자.

p11

별표 표시한 노드가 G에서 제거된 노드라 하면 이 노드를 가장 왼쪽에 추가하면 원래 그래프를 얻는다.

근데 이 알고리즘은 indegree를 계산하는데 O(n+m) 시간이 걸리고, 그걸 가지고 노드 하나를 제거하기 때문에 전체 O(nm) 시간이 걸린다. 더 빠른 방법은 없을까?

방금 본 알고리즘에서는 빨간 노드 하나를 제거하기 위해 모든 노드를 다 살펴보고 degree를 계산했다. 그리고 빨간 노드를 제거한 후에도 degree를 계산하는데 이 과정에서 전에 했던 계산을 또 해버린다. 이 과정을 줄이면 된다.

Event Queue

  • Calculate indegrees
  • Put nodes with indegree==0 in queue
  • Take node v from queue, output node v
  • Update indegrees of nodes that are linked from v
  • If a new node with indegree==0 appears, put it in the queue

indegree가 0인 노드들을 큐에 넣고 출력한다. 그리고 방금 출력된 노드와 연결된 노드들의 indegree를 업데이트에 indegree가 0으로 업데이트되면 큐에 집어넣는다.

시작할 때 모든 노드들의 indegree들을 계산하므로 (DFS) O(m+n), 모든 노드는 한 번씩 큐에 들어갔다 나오므로 O(n), 나머지 계산은 엣지의 개수에 비례하므로 O(m+n)이 되어 전체 시간복잡도는 O(n+m)이다.

A bit faster

  • Do DFS
  • Calculate post numbers
  • Output in decreasing post numbers
    • Sorting needed
  • Or, output nodes as you calculate post number
    • This is reverse order of topological sort

아까는 indegree만 계산하면 됐으므로 undirected graph에서 DFS를 해도 됐지만 지금부터는 directed graph에서 DFS를 할 것이다.

DAG에서는 엣지 방향을 지켜 전진하기 때문에 DFS 후 post number까지 붙이면 그림과 같다. (왼쪽부터 방문한다고 가정)

12

아랫쪽 노드를 방문해 번호를 붙이는 작업이 끝나야 위쪽 노드들에 번호를 붙일 수 있으므로 위로 갈수록 번호가 커진다.

여기서 주의할 점은 undirected graph에서 DFS를 하면서 엣지의 방향을 그린 것은 엣지에 방향성을 “부여”한 것이지만, directed graph면 원래 그래프의 방향이라는 것이다.

아무튼 DFS가 끝나면 post number들을 정렬해 내림차순으로 출력한다. 아니면 post number를 계산하는 순간에 노드를 출력할 수도 있다. 이 경우에는 출력된 결과는 위상 정렬의 reverse order이다.

Why does the previous work?

  • Important properties of DFS trees of directed graphs

directed graph에서 엣지들의 방향을 지키면서 DFS를 했을 때 어떤 트리가 만들어는지 보자.

13

사이클이 있을 수 있으므로 back edge도 존재할 수 있고, forward edge도 있을 수 있다. 반면 cross edge는 오른쪽–>왼쪽 방향만 가능하다. 왜냐하면 왼쪽부터 방문한다고 가정했으므로 왼쪽 –> 오른쪽으로 가는 엣지가 존재할 경우 방문을 안 했을 리가 없기 때문이다!

일반적인 directed graph에서의 DFS를 봤으니 이제 DAG에서의 DFS를 보자.

DAG DFS Tree

14

  • forward edge: 가능
  • back edge: 불가능. back edge는 cycle을 만들기 때문
  • cross edge: 오른쪽–> 왼쪽 방향만 가능

위 그래프에 post number를 붙이면 마찬가지로 왼쪽 아래로 갈수록 번호가 작다.

15

아래쪽 노드들의 번호가 작으므로 포워드 엣지는 큰 번호에서 작은 번호로 연결한다. 백엣지는 작은 번호에서 큰 번호를 연결하지만 백엣지가 존재하지 않는다. 크로스 엣지는 오른쪽–>왼쪽 방향만 존재하는데, 왼쪽으로 갈수록 노드들의 post number가 작아진다. 따라서 모든 엣지가 큰 번호에서 작은 번호 방향으로 이동한다는 것을 증명할 수 있다. 따라서 post number가 작아지는 순서로 출력을 하면 위상 정렬이 된다.

DAG에서는 DFS를 어느 노드에서 시작하느냐에 따라 트리의 개수가 달라진다.

16

그럼 트리의 개수가 최소가 되도록 하려면 어느 노드에서 시작해야 할까? 그건 알 수 없다.

SCC (Strongly Connected Component)

  • Maximal subset of nodes such that all nodes are reachable from each other
  • How do we find them?

Find SCC

  • Let’s run DFS and look at the tree
  • There are trees and cross (right -> left) edges
  • One tree may contain several SCCs
  • BUT! One SCC is in one tree

일단 DFS를 돌려보고 생각해보자. 사실 이것도 쉬운 것은 아니다. DFS를 어디서 시작할 건지, 어느 방향으로 진행할 건지도 생각해봐야 하기 때문.

하나의 SCC가 트리 여러 개에 여기저기 흩어져 있지 않음

Algorithm

  • Run DFS, set Post() numbers
  • Reverse all links
  • Run DFS
    • Starting every round at maximum Post() number possible
  • This results in each tree being one SCC

Supergraph

  • One SCC becomes one SuperNode
  • There is an Edge from SuperNode A to SuperNode B if a node in A has an edge to a node in B
  • Supergraph is a DAG

어렵다..