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

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. Bookmark the permalink. Trackbacks are closed, but you can post a comment.

14 Comments

  1. Posted 09/01/2008 at 6:32 pm | Permalink

    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. Posted 09/01/2008 at 6:48 pm | Permalink

    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. Posted 09/01/2008 at 7:07 pm | Permalink

    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. Posted 09/01/2008 at 7:21 pm | Permalink

    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.

  5. Dung
    Posted 07/03/2009 at 8:57 pm | Permalink

    Bai nay hay ghe. Em nghi mai khong ra. Giai nhu the nao ha anh Hung?

  6. Dung
    Posted 09/03/2009 at 12:29 pm | Permalink

    Em nghĩ ra rồi. Ý tưởng là xét 1 quan hệ thứ tự trên tập E các cạnh. Cạnh a < b nếu như tồn tại một walk với weight tăng dần từ a đến b. Sau đó ta chứng minh có thể phân hoạch E thành các tập con E_1,…E_m , là các tập độc lập (independent, không có 2 phần tử nào so sánh được với nhau ), sao cho E_i là maximally independent trong union từ E_i đến E_m. Các tập E_i thoả mãn thứ tự tăng dần theo lexicographical order : xét 2 tập A và B, gọi các weight của A và B theo thứ tự giảm dần là (a_1,a_2,.) và (b_1,b_2,…) thì A<B nếu a_j < b_j ở chỉ số j đầu tiên mà 2 dãy này khác nhau . Cụ thể hơn, ta luôn chọn E_i là minimal theo lexicographical order trong union từ E_i đến E_m.
    Khi đó sẽ chứng minh được là mọi phần tử từ E_j sẽ lớn hơn 1 phần tử nào đó từ E_(j-1). Lực lượng của mỗi tập E_j phải <= n-1/2, nếu không sẽ có 2 cạnh chung đỉnh và do đó so sánh được. Do đó số tập cạnh m phải ít nhất là n. Vậy phải tồn tại một walk chiều dài n.
    Với 1 graph bình thường thì độ dài walk cực đại sẽ chính là số m.

  7. Posted 09/03/2009 at 1:46 pm | Permalink

    Hi Dung,

    Lời giải rất hay! Đoạn viết về phân hoạch hơi confusing một chút.

    Dung xem thử phần đảo của định lý Dilworth và đối chiếu với chứng minh của Dung.

  8. Posted 09/03/2009 at 2:37 pm | Permalink

    Em vừa xem định lý Dilworth. Chứng minh độ dài chain bằng lực lượng của phân hoạch thành các antichain rất ngắn và hay, nhưng hơi khó nghĩ.

  9. Posted 09/03/2009 at 8:24 pm | Permalink

    Hi Dũng,

    Lời giải của tôi không dùng Dilworth, mà dùng Vizing.

    Đại khái thế này: với mỗi cạnh

    e\in E

    , gọi

    d(e)

    là chiều dài của walk-tăng dài nhất mà kết thúc ở

    e

    . Dễ thấy rằng nếu

    e

    e'

    kề nhau thì

    d(e) \neq d(e')

    . Tô màu cạnh

    e

    bằng màu

    d(e)-1

    . Do đó chromatic index của

    K_n

    nhiều nhất là

    \max_e d(e)

    . Bằng định lý Vizing (hoặc chứng minh trực tiếp cho

    K_n

    không khó gì), chromatic index của

    K_n

    với

    n

    lẻ thì bằng

    n

    . Do đó

    \max_ed(e) \geq n

    .

  10. Posted 09/03/2009 at 10:18 pm | Permalink

    Em cảm thấy có 1 cái gì đó không ổn. Trong cách của em, có một chain độ dài n không có nghĩa là có một walk độ dài n. Ví dụ n-1 cạnh xuất phát từ 1 đỉnh là 1 chain nhưng kô phải là 1 walk độ dài n-1.
    2 cạnh kề nhau cũng chưa chắc suy ra d của chúng khác nhau : ví dụ xét đồ thị trong đó 1 cạnh được nối với tất cả các cạnh còn lại : khi đó d của tất cả các cạnh là không quá 2.

  11. Posted 10/03/2009 at 6:16 am | Permalink

    Ah, Dũng nói đúng.

    Cả hai cách chỉ chứng minh được rằng có một chuỗi n cạnh với weight tăng dần (strictly), cạnh nọ kề cạnh kia trong chuỗi; nhưng như vậy không nhất thiết là có walk-tăng. Như vậy bài này vẫn “open”.

    Tôi tìm lại email cũ mà người bạn gửi bài này:

    Have you seen the following problem or something similar?

    Let n be an odd integer and let K be a complete and edge-weighted graph on n vertices. Assume that all the weights are distinct integers. Show that there is a walk of length n with monotonic weights.

    I heard about this problem or something like it before but now I can’t solve it and I’m beginning to doubt whether I remember the problem correctly. I’m just killing myself over the fact that I didn’t write it down!

    Có khả năng là đề bài không đúng :-)

  12. Posted 10/03/2009 at 1:48 pm | Permalink

    Hừm, đáng lẽ phải thấy cái này

    o----1----o
    |           |
    3           4
    |           |
    o----2----o
    

    Hai cạnh còn lại weight 5, 6.

  13. Posted 10/03/2009 at 2:19 pm | Permalink

    Hy vọng là đề bài sai :) . Điên cái đầu vì bài này. Giờ em sẽ không làm nữa, trước khi có thêm bằng chứng là nó đúng :)

  14. Posted 10/03/2009 at 3:33 pm | Permalink

    Hi Dũng, bằng chứng sai ở trên rồi đó. Xét K_4, với 6 cạnh có weights như trong hình. (Hai cạnh với weights 5, 6 không vẽ.)

    Xin lỗi vì cho đề bài sai để mất thời gian của Dũng. Và cảm ơn đã chỉ ra chỗ sai :-)

Post a Comment

Your email is never published nor shared. Required fields are marked *

*
*

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>