테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.

====== 방향 비순환 그래프 (Directed Acyclic Graph; DAG) ======

  * [[wp>Directed acyclic graph]]
  * 정리는 천천히 하자
  * 대충 키워드들만 적어두면
    * 수학적으로는 poset 에 대응된다
    * O(V+E)에 위상정렬이 가능하다
    * 위상정렬 순서대로 각종 DP문제를 풀수 있다. 보통 O(V+E)
      * shortest path도 데이크스트라나 벨만 포드보다 빠르게 그냥 O(V+E)에 계산가능
      * 일반 그래프에서는 NP인 longest path 도 DAG에서는 O(V+E)에 계산 가능 
    * transitive closure를 O(VE)에 구할수 있다
    * transitive closure 위에서 DP를 풀수도 있다
      * chain의 개수 : [[ps:problems:boj:31445]]
    * 최소경로커버 문제(모든 정점을 커버하는 겹치지 않는 최소의 경로의 수) 는 이분매칭으로 풀수 있다
    * 최소 경로 커버와 최대 반사슬 크기는 같은 값을 갖는다 (딜워스의 정리)