사용자 도구

사이트 도구


ps:dag

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

  • 정리는 천천히 하자
  • 대충 키워드들만 적어두면
    • 수학적으로는 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의 개수 : 31445
    • 최소경로커버 문제(모든 정점을 커버하는 겹치지 않는 최소의 경로의 수) 는 이분매칭으로 풀수 있다
    • 최소 경로 커버와 최대 반사슬 크기는 같은 값을 갖는다 (딜워스의 정리)

토론

댓글을 입력하세요:
H V V Y Y
 
ps/dag.txt · 마지막으로 수정됨: 2024/02/29 02:46 저자 teferi