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

14 Comments

1. Thành
   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.
   Reply
2. Ngô Quang Hưng
   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.
   Reply
3. Thành
   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).
   Reply
4. Ngô Quang Hưng
   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.
   Reply
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?
   Reply
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.
   Reply
7. Ngô Quang Hưng
   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.
   Reply
8. Dũng
   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ĩ.
   Reply
9. Ngô Quang Hưng
   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

   và

   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

   .
   Reply
10. Dũng
    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.
    Reply
11. Ngô Quang Hưng
    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
    Reply
12. Ngô Quang Hưng
    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.
    Reply
13. Dũng
    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
    Reply
14. Ngô Quang Hưng
    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
    Reply