Problem Session 6 -3부

드디어 한 문제

기나긴 여정입니다. 일단 답지 없이 해보도록 합시다.

주어진 방향 그래프(Directed Graph) G에 대해 다음 질문에 답하십시오: 

(b) G에 단일 방향 간선을 추가하여 위상 정렬이 불가능한 단순 그래프를 구성하는 간선을 제시하고, 그러한 간선의 수를 정당화하십시오.

이제 b를 풀 차례입니다. 이전 내용에서 위상 정렬을 위해서 최소한 하나의 노드의 in-degree는 0이어야 함을 보였습니다. 그렇다면? 저의 단순한 생각에는 우리의 유일한 in-degree가 0인 4에 간선(edge)을 추가해 주면 됩니다.

그렇다면, 나머지 노드가 5개니까 5개를 추가하면 되지 않을까요? 저의 답은 그렇습니다. 과연 답지는 뭐라 할까요 한번 보겠습니다. 역시나 틀렸습니다. 해답에는 4에 추가하는 것뿐만 아니라 다른 노드에도 추가해야 함을 보이고 있습니다.

아무래도 GPT가 접근하는 문제풀이 방식과 실제 문제에서 묻는 의도가 뭔가 다른 거 같습니다. 아 이래서 영어공부를 잘해서 의도를 제대로 파악해야 하는데... 사실 제가 이해한 문제의 답에는 GPT 것이 더 맞긴 합니다. 흠 찜찜하지만 어디 물어볼 사람도 없기 때문에 6-1은 이렇게 종료하도록 하겠습니다.