Một bài toán đồ thị
Ngô Quang Hưng | 09 tháng 01, 2008 | 
Bản để in
Một người bạn gửi cho bài toán sau đây. Tôi vừa tìm được lời giải rất gọn.
Cho n là một số nguyên lẻ lớn hơn 2. Mỗi cạnh của complete graph K_n được gán một cân nặng khác nhau. Chứng minh rằng có một walk chiều dài n trên graph K_n này với các cạnh có chiều dài tăng dần (strictly increasing!).
Bài này cute ghê. Cho graph bình thường cũng có thuật toán tìm walk như vậy có chiều dài dài nhất.
Chính xác! Với graph bình thường cũng làm được. Tôi trace back về một thuật toán của Lawler hồi 1976.
Không hiểu anh Hưng nói đến thuật toán nào. google thấy mỗi cái chromatic number của Lawler năm 1976, mà cái này chạy exponential. Mà bài này hình như chạy được linear time (nếu không phải sort).
Hi Thành, ý tôi nói bài tìm longest-path on a DAG. Trong sách của Lawler chứ không phải bài báo, sorry.