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
- 최소경로커버 문제(모든 정점을 커버하는 겹치지 않는 최소의 경로의 수) 는 이분매칭으로 풀수 있다
- 최소 경로 커버와 최대 반사슬 크기는 같은 값을 갖는다 (딜워스의 정리)
ps/dag.txt · 마지막으로 수정됨: 2024/02/29 02:46 저자 teferi
토론