Các bạn có thể giải bài toán về đồ thị này ?

Bạn dùng từ "chu trình" mà tôi xin lỗi chứ theo tôi hiểu thì khi vẽ đồ thị kiểu đó (có nối tất cả các điểm với nhau) thì chu trình phải được hiểu là đi qua tất cả các điểm. Tôi không nói đề bài mà nói cái bài lập luận của bạn. Không thể dùng khái niệm "chu trình" ở đây được. Nếu bạn dùng "chu trình" thì mọi người cũng sẽ hiểu như tôi thôi, co nghĩa là đi qua cả 5 điểm.

Gửi Stainless: Ở bài viết trước mình đã giải thích rõ chu trình mình cần tìm cho bạn thanh_nien_xa_vo rồi mà !

Về phương hướng giải bài này, mình nghĩ sẽ không dùng phương pháp Thử sai và quay lui đâu, vì như thế rất lâu tuy nó cho ta nhiều thông tin. Mình rất muốn dùng Toán để giải bài toán này.
Mình có học qua môn Qui hoạch tuyến tính và thấy nó giải quyết được các bài toán tương đối "khoai" như bài toán vận tải chẳng hạn. Mình biết đó chỉ là một phần của bộ môn Qui hoạch nhưng mình chưa học nhiều nên muốn lên đây để hỏi các bạn.
Ý mình định tiến hành giải bài toán theo việc đánh giá các bậc của các đỉnh. Trong bài toán của chúng ta các cạnh có số phương tiện giao thông khác nhau sẽ bị loại đi, chỉ giữ lại duy nhất một. Bậc của 1 đỉnh chính là số các cạnh khác nhau có thể nối đến nó. Trong ví dụ của mình đỉnh (1) có thể có các bậc 1 hoặc 2 chứ không thể là 3.

Vấn đề của mình là:
1. Xây dựng mối ràng buộc giữa các biến ( được gán cho các bậc của các đỉnh )
Tỉ như trong ví dụ của mình có thể lập được 1 số ràng buộc sau:
x1 + x2 + x3 + x4 + x5 = 4*2 = 8 ( 4 là số phương tiện giao thông )
x1 " {1,2}
x2 " {1,2}
x3 " {1,2}
x4 " {1,2}
x5 " {0,2}
x1 + x2 + x5 ? 3
x3 + x4 + x5 ? 3
2. Tìm thuật toán giải ( nhanh ) để xem có thể kết luận rằng liệu có trường hợp nào mà tất cả các biến mang giá trị chẵn, hay có tồn tại một biến nào đó chắc chắn mang giá trị lẻ hay không.
Các bạn có thể giúp mình được chứ !

ặ, thỏ không bĂc nào muỏằ'n giúp mơnh à ?!

Bác gì ơi, bài toán này là bài toán NP-complete, thuật giải phải chạy trong exponential time. Bác nghĩ la bài tìm chu trình Euler có thể giúp bác nhưng thực tế là không được đâu.
Muốn chứng minh bài này là NP thì bác đưa bài toán chu trình Hamilton về bài toán này. Bài toán chu trình Hamilton đơn giản answer Yes-No đã là NP rồi.
"Cho đồ thị vô hướng G, hỏi có chu trình hamilton trong đồ thị đó không."
Đưa bài Hamilton trên thành bài của bác như thế này. Tạo một graph H từ graph G như sau: Đỉnh của graph H tương ứng với các cạnh của graph G. 2 đỉnh của graph H được nối với nhau khi va 2 chỉ khi 2 cạnh tương ứng của graph G xuất phát từ một đỉnh của G. Đặt tên cho cạnh tương ứng của graph H là tên của đỉnh của graph G. Thế thì graph G có chu trình Hamilton khi và chỉ khi graph H có một chu trình đi thỏa mãn bài toán ban đầu của bác(bác chứng minh được chứ nhỉ??)
Ví dụ về graph G và H:
Graph G
(1)-------(2)
| |
| |
(4)--------(3)
Graph H được tạo thành từ G
1
(a)----------(b)
|4 |2
| |
(d)----------(c)
3
Về cách đặt bài toán theo quy hoạch tuyến tính của bác tôi nghĩ rằng chưa đủ, bởi vì bác chỉ gán bậc của mỗi đỉnh cho các biến chứ bác chưa mô tả được rằng đỉnh nào nối với đỉnh nào bằng loại phương tiện gì. Tức là điều kiện chưa chặt chẽ dẫn đến sinh ra nghiệm thừa và kết quả sai.
Được I_am_joking sửa chữa / chuyển vào 12:52 ngày 20/07/2004

Cảm ơn bạn I_am_joking,
Đúng là bài toán mình nêu ra tương đương là bài toán NP-complete, nhưng đó là việc tìm ra chu trình Euler thỏa mãn yêu cầu bài toán. Còn mình chỉ yêu cầu là: Trả lời câu hỏi "Có tồn tại hay không chu trình thỏa mãn yêu cầu của bài toán hay không thôi" ( cái này mình có nói rõ và đã nói nhiều lần ).
Cho phép mình đính chính: Ở bài trên x5 " {0,1,2} chứ không phải x5 " {0,2}

Thế bạn đã đọc bài tôi chưa đấy? Tôi khẳng định là bài toán "có tồn tại hay không" chu trình như trên đã là là NP rồi. Bởi vì như tôi nói rồi đấy bài toán "tồn tại hay không một chu trình Halminton" đã là NP rồi.
Mong bạn đọc kỹ lại bài tôi. Bạn không thể tìm ra cách đơn giản để giải bài toán trên đâu. Với input nhỏ thì bạn thử sai, quay lui. Còn input lớn chỉ có thể xài heuristic thôi.
Thân.

Không biết bạn đang học phổ thông hay đã lên đại học rồi? Tôi nói thêm cái này. Muốn chứng minh một bài toán là NP thì ta đưa một bài toán NP khác về bài toán đó. Tôi chọn bài toán "có tồn tại chu trình Hamilton không?" để chứng minh bài toán của bạn là NP.
Được I_am_joking sửa chữa / chuyển vào 00:26 ngày 22/07/2004

Rất xin lỗi I_am_joking vì đã không đọc kĩ bài viết của bạn,
Đúng như bạn nói, bài toán của mình đưa về: "tồn tại hay không một chu trình Hamilton của 1 đồ thị vô hướng". Nhưng mình không biết bài toán này là NP. Mình nhớ là đã đọc ở đâu đó rằng: "Chưa tìm ra phương pháp tốt xác định một đồ thị vô hướng có chu trình Hamilton hay không".
Bạn xem lại được chứ ! Nếu có thể bạn trích chỗ nói rằng bài toán "tồn tại hay không một chu trình Hamilton của 1 đồ thị vô hướng" là NP nhé.
À, vote cho I_am_joking 5 * vì sự nhiệt tình của bạn !

Bạn xem chương 36 của cuốn "Introduction to algorithm" second e***ion của MIT press.
http://mitpress.mit.edu/catalog/item/default.asp?tid=8570&ttype=2
Trong chương này có chứng minh các bài toán sau đây là NP-hard
(Hình được lấy từ chương 36, Introduction to algorithm, 2nd e***ion, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, MIT press)
Cuốn này chứng minh NP-hard cho decision problem(có tồn tại hay không?) chứ không phải chỉ cho optimization problem không đâu. Nhà xuất bản Ngọc Anh Thư có dịch ra tiếng Việt quyển này tựa là Cẩm Nan Thuat Toán. Nhưng tôi nghĩ đừng đọc bản tiếng Việt làm gì. Bạn muốn lấy ebook thì pm cho tôi, tôi gởi cho.