Problem Session 6 -2부
이어서
주어진 방향 그래프(Directed Graph) G에 대해 다음 질문에 답하십시오:
(a) G의 위상 정렬을 제시하고, G의 서로 다른 위상 정렬의 수를 정당화하십시오.
(b) G에 단일 방향 간선을 추가하여 위상 정렬이 불가능한 단순 그래프를 구성하는 간선을 제시하고, 그러한 간선의 수를 정당화하십시오.
자 그럼 다시 시작합니다
단 두 가지만 있으면 풀린다. (a)
첫 번째 문제는 두 가지만 있으면 풀 수 있습니다.
첫째는, 지난 시간에 다룬 것처럼 어떤 노드가 Topo sort의 시작노드가 될 수 있는지?를 답하면 되고
둘째는 실제 구현 아이디어인데, 시작 노드를 구했다면 해당 노드를 삭제했을 때 그다음 in-degree가 0인 노드가 무엇인지?
이 두 가지를 반복하면 위 문제는 쉽게 풀 수 있습니다. 어떻게 설명해야 할지 상당히 고민했지만 이게 가장 손쉬운 답변입니다.
첫째, 어떤 노드가 Topo sort의 시작 노드가 되는가?
해당 수업에는 무수히 많은 수학적 귀납법과... 그.... 역설을 배반함으로써 증명하는 그런 방법이 나옵니다. 그럼 어떤 노드가 Topo sort의 시작노드가 될 수 있는지는 다음과 같은 claim에서 시작할 수 있습니다.
Claim : in-degree가 0인 노드만이 시작노드가 될 수 있다.
얼핏 보면 맞는 말인데, 이게 진짜 논리적으로 맞는지 증명하는 게 참 까다롭습니다. 제가 틀릴 수도 있지만 그래도 한번 이야기해 봅니다.
Contradiction : in-degree가 0이 아닌 노드(1 이상)는 topo-sort의 시작 노드가 될 수 있다
증명
in-degree가 1 이상인 노드를 Topo Sort의 시작 노드로 삼는다.
하지만 해당 노드를 가리키는(위상상 그 이전에 있는) 노드가 있다.
Topo Sort는 위상이 낮은 순서에서 높은 순서로 정렬한다.
그렇기 때문에 현재 노드가 아닌 최소한 그 이전 노드가 Topo Sort의 시작 노드가 된다.
따라서, in-degree가 0이 아닌 노드는 Topo Sort의 시작 노드가 될 수 없다.
다시 말해, in-degree가 0인 노드만이 Topo Sort의 시작 노드가 될 수 있습니다. 이로써 첫 번째, 어떤 노드가 Topo Sort의 시작 노드가 되는지 증명했습니다.
두 번째, 시작노드 삭제 Recursion
이제 메인 알고리즘을 이야기해 봅시다. 결국 해야 할 것은 in-degree가 0인 노드를 계속 따라가는 것입니다. 그래프를 이렇게 이해해 보면 쉽습니다. in-degree가 0인 노드와 그 subgraph로 이해하면 됩니다. 그림으로 이해해 봅시다.
주어진 문제에서 in-degree는 최초에 다음과 같이 주어져 있습니다. 그리고 4에서 시작한다는 것은 앞의 1번을 통해 알고 있습니다. 그럼 4번에 볼일은 끝났고, 이제 이 노드를 떼어낸다고 생각해 봅시다. 떼어내면서 연결된 out-edge도 없애게 됩니다. 그렇다면 전체적인 그림은 어떻게 될까요?
이렇게 됩니다. 각 노드의 입장에서는 in-edge가 없어졌기 때문에 in-degree가 하나씩 줄어들게 됩니다. 위 그림의 경우 4의 이웃이었던 1,2,3의 degree가 줄어든 것을 볼 수 있습니다. 이제 2를 떼어봅니다.
그럼 위와 같이 생깁니다. 근데 in-degree가 같은 경우를 볼 수 있습니다. 그러니까 0과 1중 누군가를 먼저 놓아야 합니다. 여기 문제에서는 각기 고유한 개수를 세는 거기 땨문에 숫자에 집중합시다. 그럼 쉽게 0이 두 개니까 2개의 조합이 있는 것입니다.
첫 번째는 0의 subgraph를 먼저 해결하는 것이고 두 번째는 1을 먼저 해결하는 것입니다. 근데 0의 경우 0을떼네면 그다음 neighbor들도 0이 됩니다. 따라서 2개의 케이스가 나옵니다. 그럼 모든 경우의 수를 구해보면 아래와 같습니다
1(Node 4) * 1(Node 2) * 2(Node 0,1 선택) * 2(Node 3,5 선택) = 4가 됩니다.
자 그럼 답을 맞혔을까요? 정답은 틀렸습니다... 일단 덮어 놓는데, 알고리즘 구현 측면에서는 4가 더 맞는 거 같습니다. 자세한 설명은 답지에 있고, 시간 관계상 다음 글에선 (b)로 넘어가도록 하겠습니다.
