비방향 그래프에서는 최대 V-1 개의 엣지가 가능하다. spanning tree이다. 그 이상 연결하면 반드시 사이클이 생긴다.
방향 그래프에서는 Topological sort를 고려한다고 생각해 보면 맨 앞에서는 V-1개 , V-2 ... 1 의 총합은 V(V-1)/2 개이다.
'Programming Problems > Graph' 카테고리의 다른 글
| 셋 전부 합치기 Q (0) | 2018.04.22 |
|---|---|
| 사이클 없는 그래프에서 각 점에의 최대 트래픽 찾기 Q (0) | 2018.04.22 |
| 배열 스왑해서 정렬하기 (BFS 응용) (0) | 2018.04.17 |
| 끝말잇기 문제 (오일러 경로) (0) | 2018.04.17 |
| DFS로 보드 길 찾기(그래프 변환) (0) | 2018.04.17 |