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

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

Đề bài như sau:
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...
Câu hỏi đặt ra là: 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 ?

Yêu cầu: Thời gian chạy chương trình là ít nhất có thể. Chỉ cần trả lời là có tồn tại chu trình thoả mãn yêu cầu bài toán hay không, không phải chỉ ra chu trình.

Ví dụ:
Cho đồ thị sau, gồm có các phương tiện giao thông là: a, b, c, d.



Trả lời: Có tồn tại chu trình thoả mãn yêu cầu bài toán.
( Ví dụ: (1)->(3)->(4)->(2)->(1), các phương tiện giao thông lần lượt được sử dụng là: b, c, d, a )

Liệu các bạn nào giỏi về lập trình có thể đánh giá độ phức tạp thuật toán của bài toán trên không ?

Cảm ơn các bạn đã tham gia topic của mình. Rất mong nhận được những ý kiến quí báu từ các bạn !

JB

đây là bài toán quy hoạch nguyên
dạng tìm đuờng đi ngắn nhất
có một bài toán điển hình cho dạng này là bài toán người bán hàng
lên google đánh chữ "saleman travelling" có cả núi lời giải, source code....
nhưng ở đây phải xét các chặn đừong như là các trạm mà người bán hàng đi qua. tuy nhiên để chỉ sử dụng một loại phương tiện thì thêm dzô ràng buộc như sau
đối với phương tiện a
đặt x1 là biến cho biết người bán hàng có đi từ 1-5 hay không?
tương tự có x2, x3
và x1,x2,x3 chỉ nhận giá trị 0:không đi 1:đi
=> ràng buộc đuợc đặt như sau
x1 + x2 + x3 =1
tương tự với các loại phương tiện khác
tui nói dzậy hông biết có trúng y bạn không
có gì trao đổi thêm đi
chào

Bạn cần định nghĩa rõ hơn một chút: chu trình là gì:
1. Là một hành trình khép kín (nghĩa đen của chữ chu trình) và đi qua tất cả các nút,
2. Là một hành trình đi qua tất cả các nút, không cần khép kín, hay
3. Là một hành trình đi qua tất cả các nút, mỗi nút đúng một lần.
Sau khi bạn có một đề bài rõ ràng, tôi nghĩ mọi người mới có thể tham gia được

độ phức tạp của bài toán trên là bằng không.
Quá dễ.Chỉ cần dùng thuật quay lui đơn giản là ra thậm chí còn tất cả các đáp số.

cu mèo xám: tui không nói nó khó
nhưng nó có nhiều cách giải và nhiều giải thuật khác nhau để giải. bài này không chỉ có đệ quy lùi không đâu mà còn các giải thuật khác như ủ kim loại, vùng cấm, các giải thuât kinh nghiệm khác nữa ....
giải một bài nhưng biết nhiều cách giải cho mấy bài khác cũng thú lắm
nhưng bài toán dạng travel saleman trên thế giới này chưa ai đủ tự tin là mình có thể giải ra tất cả đáp số của nó đâu=>tui thấy ông nói wá rùi đó
bây giờ thử tăng ràng buộc lên 200 thành phố và 50 loại phương tiện đi xem có giải được không?

Rất cảm ơn các bạn đã tham gia Topic của mình. Ban đầu mình cũng tưởng không ai quan tâm đến nhưng hôm nay mở ra thấy vậy thì mình xúc động lắm.
Gửi bạn octobersky: Bạn nói đúng ý mình đó. ( Có phải x2, x3 là dành cho các cạnh 1-2 và 2-5 ? )
Gửi bạn thanh_nien_xa_vo: Chu trình mình nói là một cách đi xuất phát từ 1 đỉnh, sau khi 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 thì quay về đỉnh xuất phát.
Nhưng các bạn để ý là mình chỉ muốn trả lời câu hỏi có tồn tại chu trình hay không thôi. Vì nếu phải tìm ra cụ thể là chu trình nào thì bắt buộc phải dùng thuật toán quay lui, với trường hợp đồ thị lớn thì lâu lắm !
Mình nghĩ như thế này:
Trước tiên ta gọi rằng các cạnh có dùng 1 loại phương tiện giao thông là các cạnh trùng nhau.
Để tìm xem đồ thị có tồn tại chu trình thỏa mãn yêu cầu bài toán hay không thì ta phải loại bớt các cạnh trùng đi. ( Ý của mình là muốn áp dụng định lý "Tồn tại hay không 1 chu trình Euler của 1 đồ thị vô hướng" để giải bài toán này )
Sẽ có 2 trường hợp xảy ra:
1. Trong quá trình loại có xuất hiện đỉnh có bậc chắc chắn là lẻ. Ta kết luận luôn là không tồn tại chu trình thỏa mãn yêu cầu bài toán.
2. Tồn tại ít nhất một trường hợp mà tất cả các đỉnh của đồ thị đều có bậc là chẵn. Ta cũng kết luận luôn là có tồn tại chu trình thỏa mãn yêu cầu bài toán.
( Ở đây, lưu ý với các bạn là bậc của một đỉnh của đồ thị đặc biệt này chưa thể được xác định luôn, nó còn phụ thuộc vào việc ta loại cạnh trùng nhau như thế nào. Ví dụ trong ví dụ của mình, đỉnh (1) có thể có bậc 1 khi ta loại cả hai cạnh a nối với nó đi mà cũng có thể có bậc là 2 khi ta giữ lại một trong hai cạnh a đó )
Vấn đề là ta loại các cạnh trùng nhau như thế nào ?
Mình chưa tìm ra được cách loại cạnh tối ưu nhưng theo mình ta nên đi theo con đường sau: Loại các cạnh trùng nhau sao cho số các đỉnh có bậc chẵn là nhiều nhất có thể.
Xin các bạn xem lại ví dụ mà mình đã đưa ra:

Nhìn vào đỉnh (1) ta thấy chắc chắc nó phải nằm trên đường đi của một chu trình thoả mãn yêu cầu bài toán ( nếu có ) vì nó là 1 đỉnh của cạnh b duy nhất. Hiện tại nó nối tới 3 cạnh có nhãn lần lượt là a, a và b. Như vậy để (1) có số bậc là chẵn thì 1 trong 2 cạnh a phải được giữ lại. Như vậy thì cạnh a nối 2 đỉnh (2) và (5) chắc chắn là sẽ bị loại.
Lập luận tương tự, ta loại cạnh c nối 2 đỉnh (3) và (5).
Nhìn vào đỉnh (2) ta thấy nó nối 2 cạnh a và d. Như vậy để đỉnh (2) có bậc là chẵn thì cạnh a nối 2 đỉnh (2) và (1) phải được giữ lại. Điều đó có nghĩa là cạnh a nối 2 đỉnh (1) và (5) chắc chắn bị loại.
Lập luận tương tự, ta loại cạnh c nối 2 đỉnh (4) và (5).
Như vậy, đồ thị ban đầu còn lại 4 đỉnh (1), (2), (3) và (4), nối với nhau bởi các cạnh mầu đen. Ta thấy tất cả các đỉnh này chắc chắc đều có đỉnh là chẵn. Như vậy, ta kết luận là tồn tại chu trình thoả mãn yêu cầu bài toán.
Trên đây mình chỉ lập luận với một ví dụ hết sức đơn giản. Vấn đề là phải tìm ra thuật toán chung đối với một đồ thị tổng quát để mà có thể lập trình được, và tất nhiên cũng phải đảm bảo thời gian chạy chương trình là nhanh nhất có thể nữa. Rất mong được các bạn tham gia giúp sức.

tui thấy dzậy rất hay á
nhưng lập trình đưa lên máy tính làm sao để thể hiện mấy cái này
hiện mấy sách tin học có chỉ lập trình có bài này không há
tui thấy nó cũng giống như một bài toán mà tui học trong chương trình là bài "travelling saleman" (ở tiếng việt là người bán hàng hay người giao hàng, báo...) trên mạng nhiều source code lắm.
có gì tham khảo thêm hé

Bài toán "Salesman travelling" thì mình cũng có biết, thực chất của bài toán này là tìm chu trình Hamilton: xuất phát từ một đỉnh, đi qua tất cả các đỉnh còn lại, mỗi đỉnh qua đúng một lần sau đó trở về đỉnh xuất phát.
Đúng là bài toán mà mình đặt ra có độ khó ngang với bài toán "Salesman travelling" trong việc tìm ra một chu trình cụ thể thoả mãn yêu cầu của bài toán. Nhưng mình chỉ muốn trả lời cái câu hỏi là có tồn tại ít nhất một chu trình đó hay không thôi ! Rất may là có định lý "Tồn tại hay không 1 chu trình Euler của 1 đồ thị vô hướng" trợ giúp cho bài toán của mình ( Mình xin nhắc lại định lý này: Cho một đồ thị vô hướng G liên thông và có hơn một đỉnh. Thì G có chu trình Euler nếu và chỉ nếu mọi đỉnh của G đều có bậc là chẵn ).
Mình muốn lập một hệ phương trình nào đó để giải ( tựa như phương pháp Qui hoạch chẳng hạn ). Có thể ta lấy bậc các đỉnh của đồ thị làm các biến, xây dựng mối ràng buộc giữa chúng; sau đó ta tìm ra thuật toán để làm sao rút ra kết luận liệu có tồn tại một trường hợp sao cho giá trị các biến đều là chẵn cả hay không ?

Lập luận dài dòng đi đến một kết quả gây cười cho thiên hạ. Chán không chịu được.
Nếu làm như thế thì coi như vất đỉnh (5) đi. Thế thì tự nhiên vẽ cái (5) vào làm quái gì cho nhức mắt?
Nếu đề bài toán có (5) thì kết luận là không được
Nếu không có 5 thì việc quái gì phải lập luận dài dòng. Nhìn cái là thấy.

Gửi Stainless: Chắc chắn bạn chưa đọc kĩ bài toán mà tôi nêu ra rồi.
Với cả tôi muốn tìm thuật toán để giải cho một đồ thị bất kì chứ không phải với ví dụ đơn giản mà tôi đã nêu.
Mong bạn xem kĩ lại và cho ý kiến.
Cảm ơn bạn !