Solutions of Edge direction

Select solution language

chithanhnguyen Created at 4 likes

Tạm bỏ qua các cạnh vô hướng, ta dựng đồ thị $G$ với các cạnh có hướng. Trước hết ta có nhận xét: **Nhận xét.** Nếu $G$ không phải là một DAG (đồ thị có hướng không chu trình) thì không có phương án thỏa mãn. Chứng minh của nhận xét trên khá hiển nhiên do việc thêm cạnh không thể loại bỏ chu trình. Đối với trường hợp $G$ là DAG, ta luôn có thể xây dựng một phương án định hướng cạnh thỏa mãn. Cụ thể, ta dựng đồ thị theo các bước sau: - Thực hiện sắp xếp tô-pô trên đồ thị $G$ bằng DFS hoặc thuật toán Kahn. - Dựa vào thứ tự tô-pô, ta đánh số $pos[i]$ là vị trí của đỉnh $i$ trong thứ tự tô-pô - Xét các cạnh vô hướng $(u, v)$, - Nếu $pos[u] < pos[v]$, ta định hướng cạnh này thành $u\rightarrow v$ - Nếu $pos[u] > pos[v]$, ta định hướng cạnh này thành $v\rightarrow u$ Như vậy thứ tự tô-pô ta thu được ở bước 1, cũng là một thứ tự tô-pô hợp lệ của đồ thị mới thu được. Vì đồ thị mới tồn tại thứ tự tô-pô, nên nó luôn là DAG.