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

Hà hà, vừa suy nghĩ ra cái này.
Cho một đồ thị vô hướng. Mỗi khi đi chuyển từ đỉnh này đến đỉnh kia người ta phải đi đúng một phương tiện giao thông nhất định. Ta kí hiệu các phương tiện đó bằng các chữ cái thông thường a, b, c...
Bài toán 1: tìm một chu trình sao cho ta sử dụng được tất cả các loại phương tiện giao thông, trong đó mỗi loại phương tiện được sử dụng đúng một lần ?
Bài toán 2: Liệu có tồn tại một chu trình sao cho ta sử dụng được tất cả các loại phương tiện giao thông, trong đó mỗi loại phương tiện được sử dụng đúng một lần ?
Giờ giả sử bạn biết rằng Bài toán 1 là NP complete nhé. Giờ bạn tự hỏi là bài toán 2 có phải là NP-hard hay không?
Tôi sẽ chứng minh bài toán 2 cũng là NP bằng phản chứng như sau:
Giả sử tồn tại thuật giải T có thể trả lời cho bài toán 2 trong polynomial time. Ta sẽ dùng T như một routine cho thuật toán sau (thuật toán này trả lời câu hỏi của bải toán 1).
Đầu tiên hỏi T có tồn tại chu trình không? T trả lời KHÔNG thì trở về. T trả lờ có thì TIẾP TỤC chạy phần phía dưới.
Duyệt hết tất cả các cạnh e của graph G(input).
delete e ra khỏi G, hỏi T xem graph G có chu trình thoã mẵn bài toán đặt ra không?
nếu T trả lời là CÓ thì tiếp tục duyệt các cạnh khác. Nếu T trả lời KHÔNG thì gắn e trở lại vào G rồi tiếp tục duyệt các cạnh khác.
Graph G khi chạy xong thuật toán trên sẽ là chu trình thoã măn đề bài. Và thuật toán trên chạy trong polynomial time nếu T chạy trong polynomial time. Vậy thì T không thể chạy trong polynomial time được.
Được I_am_joking sửa chữa / chuyển vào 12:49 ngày 22/07/2004

Rất xin lỗi I_am_joking vì mình đã không trả lời bạn sớm. Dạo này mình quá bận, máy tính ở nhà lại hỏng ( tất nhiên không hẳn là không có time để post bài mà là thiếu time để suy nghĩ kĩ về bài toán của mình ).
Mình thấy khâm phục kiến thức và sự nhiệt tình của bạn, chắc bạn đang là sinh viên học tập ở nước ngoài ?

Về bài toán đồ thị này, với mình thực sự không có tham vọng tìm ra thuật toán đa thức để trả lời câu hỏi "có tồn tại chu trình thoả mãn hay không" ( vì nếu có chắc đã có người tìm ra ). Mình chỉ hi vọng nó sẽ mở ra một hướng để tiếp cận với cách trả lời nhanh câu hỏi đó ( tựa như thuật toán tham lam chẳng hạn ). Với câu hỏi "một đồ thị vô hướng có chu trình Hamilton hay không" thì ta gần như không có "manh mối" nào cả. Tuy nhiên với bài toán của mình đưa ra thì ta có thể sử dụng định lý về sự tồn tại chu trình Euler ( đó là tồn tại trường hợp sao cho "bậc" của các đỉnh đều chẵn ).
Nói tóm lại là mình muốn dùng định lý về sự tồn tại chu trình Euler để xây dựng một hướng để trả lời về sự tồn tại chu trình Hamilton !
Đợt tháng 12 năm ngoái có một vị giáo sư người Mĩ sang bên trường mình và có bài giảng về chu trình Hamilton. Do vốn tiếng Anh quá nghèo nàn nên mình không hiểu gì cả. Nhưng mình cũng chỉ mang máng biết được là bài toán về chu trình Hamilton chỉ có thể giải bằng cách tiếp cận nó ( cách của giáo sư đưa ra là dùng phương pháp 3 chiều gì đấy : Hamilton cycles in prisms over graphs ). Vì thế mình rất mong muốn phương án mình đưa ra có thể có đôi chút hữu ích.
Bạn có thể tìm hiểu xem có các phương pháp nào đã được đưa ra và giúp mình xây dựng bài toán này chứ !

Hà hà. Hiện giờ tôi cũng có bài toán của tôi cần giải quyết. Nếu bạn nói cho tôi nghe mục đích nghiên cứu bài toán này (bạn định viết paper, bạn đang làm tiểu luận, bạn chỉ tò mò...) thì có thể tôi sẽ tham gia với bạn....=).

Mục đích của mình thật ra cũng không cụ thể gì cả, chỉ đơn giản là thích thì tìm hiểu thôi.
Bạn có thể đào sâu vào để xem liệu hướng chúng ta đi đã có ai đi chưa, liệu có thể mang lại kết quả chi không... Mình thì vốn kiến thức hẹp hòi nên bấy lâu nay "thai nghén", không làm ăn thêm được chi cả.
Nếu bạn thấy phương án đưa ra là khả thi thì lúc đó thiếu gì mục đích để chúng ta làm, phải không ?

Kiến thức của tớ cũng không nhiều. Nhưng không sao, chỉ cần thích khám phá là đủ rồi, kiến thức sẽ dần dần mà có trong quá trình tìm hiểu về bài toán. Tuy nhiên hiện giờ tớ đang có một bài toán khác, cần giải quyết xong mới làm chuyện khác được. Nếu cậu muốn thì đợi 4 tháng nữa tớ với cậu lại thảo luận tiếp nhé? =)

Giỏi lắm,nhưng là giỏi lập trình,bà con co thể dùng cái đầu của mình và giấy mực để giải đươc không?
tôi có môt bài toán như sau
CMR tổng các căn bậc 3 của 2 ,4 và 8 là một số vô tỉ
dễ quá phải không,nhưng tôi muốn anh em tìm lời giải hay nhất sau không quá 1 tuần.Chấp ông joking chơi lập trình đó

Mạn phép joking, tui thử đưa ra lời giải trước xem thế nào.
Đầu tiên, tui đưa ra các tiên đề:
- tổng một số với một số hữu tỉ là vô tỉ khi và chỉ khi số đó là vô tỉ
- tích (thương) một số với một số hữu tỉ là vô tỉ khi và chỉ khi số đó là vô tỉ
Các bác kiểm tra lại hộ em bằng phản chứng cái nhé.
Căn bậc 3 của 8 là 2, vậy ta chỉ cần chứng minh tổng căn bậc 3 của 2 và 4 là số vô tỉ. Ký hiệu root3(x) là căn bậc ba của x. Xét tổng 1 + root3(2) + root3(4) = 1 + a + a^2 = (a^3 - 1)/(a - 1) = 1/(a-1) trong đó a = root3(2).
Rõ ràng a là vô tỉ, suy ra (a-1) cũng là vô tỉ, và 1/(a-1) cũng rứa. Lần ngược ta có là root3(2) + root3(4) + root3(8) là vô tỉ.

joking à, vậy nhờ bạn đánh giá liệu mình cứ theo tìm hiểu về vấn đề này thì có thu được kết quả gì không. Vì mình cảm thấy lao vào nó cứ như là đánh bạc vậy, chắc bạn hiểu.
joking cứ nói thật quan điểm, đừng ngại.

cậu làm hay lắm,nhưng cậu có chắc đó là cách ngắn nhất ko???

Trời làm nghiên cứu thì làm sao mà nói trước được hả bác? Có khi bác nghiên cứu cái này nhưng mà cuối cùng lại tìm ra cái khác. Nhưng mà nói thật là mấy bài như thế này thì em không thích lắm, nó theoretical quá và người ta cũng tìm hiểu nhiều rồi. Tìm những bài mới (nhưng đừng mới quá khó tìm tài liệu) làm thì dễ hơn phải không bác? Bác thích làm về lĩnh vực gì thì search paper với các tạp chí chuyên ngành của lĩnh vực đó mà đọc. Đọc khoảng 2-3 tháng, ngày nào cũng đọc thì sẽ tìm được đề tài nghiên cứu thôi,
Mà em đang học undergraduate thì kinh nghiệm làm nghiên cứu cũng không nhiều. Bác hỏi các bác graduate thì sẽ biết rõ hơn.