방향 그래프 요약

요약

• 방향 그래프는 모든 간선이 방향간선인 그래프를 말한다.
• 방향그래프 G의 어느 두 정점 u와 v에 대해서나 u와 v에 도달하며 v는 u에 도달하면 G를 강연결이라고 말한다.
• 동적프로그래밍은 언뜻 보기에 많은 시간이 소요될 것 같은 문제에 주로 적용한다. 적용에 적당한 문제들은 공통적으로 부문제 단순성, 부문제 최적성, 부문제 중복성 등 세 가지 특성을 가진다.
• 방향 비싸이클 그래프는 방향싸이클이 존재하지 않는 방향그래프를 말한다.
• 방향그래프의 위상순서는 모든 i < j 인 간선 $(v_i,v_j)$에 대해 정점들을 번호로 나열한 것을 말한다.
• 위상 정렬은 DAG로부터 위상순서를 얻는 절차를 말한다. 진입차수를 이용하는 방법과 DFS를 특화해서 얻는 방법 등 두가지 방식이 있다.