비순환 그래프 간선 방향 정하기 (Edge Orientation on Acyclic Graphs)
이번에 살펴볼 문제는 간단하지만 흥미로운 문제입니다. 우리에게 어떤 방향이 없는 그래프 \(G = (V, E)\)가 주어졌습니다. 이제 이 그래프의 어떤 간선 \((u, v) \in E\)를 \( \langle u, v \rangle \)이나 \( \langle v, u \rangle \)와 같이 방향을 주도록 합시다. 방향을 주는 방법은 여러 가지가 있겠지만, 그중에서 우리는 각 정점마다 들어오는 간선의 개수를 최소화 시키는 것을 구해보고자 합니다. 좀더 엄밀히 말하자면, \(G = (V, E)\)가 주어졌을 때, 우리의 목표는 각 간선 \( (u,v) \in E \)에 대해, \( \langle u, v \rangle \in A \)이거나 \( \langle v, u \rangle \in A \)를 ..
