Một bài toán đồ thị

Ngô Quang Hưng | 09 tháng 01, 2008 | Bản để in 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!).

Chủ đề: Combinatorics |

4 lời bình cho bài “Một bài toán đồ thị”

  1. 1
    Thành viết:

    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.

  2. 2
    Ngô Quang Hưng viế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.

  3. 3
    Thành viết:

    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).

  4. 4
    Ngô Quang Hưng viết:

    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.

Ghi lời bình của bạn: