해당 글은 Algorithms. by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani를 정리한 스터디 노트입니다.해석하면서 정리한 글입니다.

3.3 Depth-first search in directed graphs

3.3.1 Types of edges

• 노드 관점의 연결관계
  • 탐색 트리의 root: 제일 상위인 노드를 말합니다. (A)
  • 노드의 descendant: root 노드보다 하위일 때 (A를 제외한 나머지 항목)
  • 노드의 ancestor: (E는 F,G,H 노드의 조상)
  • 한 directed edge에 대한 양쪽 노드가 서로 parent, child관계입니다.(C는 D node의 부모이자, D node는 C의 자식)

• 엣지 관점의 연결관계
  • tree edges: DFS 포레스트의 실제 solid한 실제 edge를 의미합니다.
  • 아래는 가상의 엣지라고 볼 수 있습니다.
    • forward edges: 상위 노드가 nonchild descendant 노드로 가는 edge.
    • back edges: 하위 노드가 ancestor 노드로 가는 edge.
    • cross edges: neither descendant nor ancestor 노드 관계에서 가질 수 있는 edge.

• pre/post in directed graph
  • edge($u, v$)에 대한 타입을 노드의 pre/post 구간값을 통해 알 수 있습니다.
    • $[u[v v]u]$: 기존에 저희가 학습했던 구조입니다.($u$ -> $v$)
      • Tree/forward edges
    • $[v[u u]v]$: $v$->$u$
      • back edges
    • $[u u]$ $[v v]$: 상관이 없는 구조입니다.
      • Cross edges
  • $u$가 상위, $v$가 하위 단계로 연결되어 있으면, $pre(u) < pre(v) < post(v) < post(u)$ 라고 볼 수 있습니다.

3.3.2 Directed acyclic graphs

그래프에 cycle이 존재한다는 것은 circular path($v_0 -> v_1 -> v_2 -> … -> v_k -> v_0$)가 존재한다는 뜻 입니다.
그리고 cyclic이 아닌 그래프를 acyclic 이라고 합니다.

Property driected graph가 cycle이 있다는 것은 그 그래프의 DFS가 back edge를 찾아내는 것과 동일합니다.
proof) (u, v)라는 back edge가 있다고 하겠습니다. 그러면, v에서 u로 가는 path와 함께 cycle 구성이 가능해집니다. 다음엔 cycle이 있다고 가정하겠습니다. 따라서 DFS에 의해 가장 작은 pre number에 대해, 첫번째로 발견되는 노드가 있습니다. cycle에 있는 다른 노드들은 모두 그 첫번째 발견된 노드의 descendants입니다. 특히, 직전 노드는 ancestor로 향하는 노드이기 때문에, back edge의 정의에 해당합니다.

Directed acyclic graphs(Dags)는 causalities, hierarchies, temporal dependencies과 같은 관계를 모델링하는데 유용합니다.
“어떤 유효한 순서로 작업을 해야할까?”와 같은 문제를 모델링합니다.
각 노드가 하나의 작업이고, 엣지 u->v 는 v의 선행으로 u가 작업되어야 한다는 것으로 표현이 가능합니다. (만약 cycle 구조라면, 순서는 의미가 없습니다.)

만약 dag(Directed acyclic graph) 구조라면, linearize(or topologically sort)를 통해 순서를 표현할 수 있습니다.
어떤 형태의 dag 구조든 모두 linearize가 가능합니다. DFS를 통해 linearize한 순서를 찾을 수 있습니다. DFS를 통해 나온 post numbers를 내림차순으로 vertex를 나열하면 끝납니다. 즉, 마지막 훑은 애가 가장 상위노드라는 의미입니다.

property dag에서, 모든 edge는 작은 post number를 가진 노드로 향합니다.
dag형태에서는 back edges형태를 가질 수 없습니다. (post number가 흐르는 방향을 생각하면 됩니다)
이 성질로 인해, dag의 노드들을 순서화하는데 linear-time algorithm으로 생각할 수 있습니다.
acyclicity, linearizability, the absence of back edges during a DFS 이들은 dag의 세가지 속성을 말해주는 성질입니다.

dag는 post numbers를 감소시킴으로써 linearized 되므로, 이 선형화에서 post number가 가장 작은 정점이 마지막으로 와야하며, 그것은 나오는 엣지가 없는 sink가 됩니다.

• highest post number 노드가 source
• smallest post number 노드가 sink

Property 모든 dag는 적어도 하나 이상의 source와 하나 이상의 sink를 가집니다. 즉, 입출노드가 하나 이상은 있습니다.
source의 존재를 통해, linearization을 다른 방식으로 접근할 수 있습니다.(linear time operation 증명필요) 1) source를 찾고, 출력하고, 그래프에서 삭제합니다. 2) 그래프가 빌 때까지 반복합니다.

이게 모든 dag에 대해 성립할 수 있는 이유는 위의 성질에 따라 모든 dag는 하나 이상의 source가 존재하기 때문입니다.

Reference

1. Algorithms. by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani(http://algorithmics.lsi.upc.edu/docs/Dasgupta-Papadimitriou-Vazirani.pdf)