Tìm một đồ thị con Euler của đồ thị ban đầu G

[shuto_uke]

Mình có bài toán sau muốn hỏi các bạn:
"Tìm một đồ thị con Euler của đồ thị ban đầu G. Tập nhãn trên các cạnh của đồ thị đó là tập nhãn của đồ thị G, và không có 2 cạnh nào có nhãn trùng nhau."
Mong nhận được những ý kiến đóng góp từ các bạn !

[Pateheo]

Bạn có biết định lý về điều kiện cần và đủ để một dồ thị là đồ thị Euler không? Đại khái nó thế này:"G là đồ thị Euler<=>liên thông& tất cả các đỉnh đều bậc chẵn.".
Như vậy, điều kiện đầu tiên phải xét là xem G có đủ các điều kiện nêu trên không.
Nếu có, chắc chắn nó tồn tại chu trình Euler.
Tiếp theo, đơn giản dùng các thuật toán duyệt đồ thị như DFS,BFS để duyệt G.mỗi lần bạn đụng phải đỉnh bắt đầu duyệt thì dừng lại. Xoá hết các cạnh đã đi qua (kết quả là các bậc của các đỉnh sẽ giảm xuống). Duyệt lại toàn bộ số bậc của các đỉnh. Đỉnh nào còn bậc thì cứ việc thừ đó mà duyệt DFS/BFS tiếp.
Cách chèn các chu trình con lại với nhau có thể dùng kỹ thuật về LinkedList.
Các tài liệu tham khảo vấn đề này có thể tìm thấy ở các sắch sau:
-Toán rời rạc và ứng dụng trong tin học (Keneth Rosen)
-ỈNtoduction to Algorithm (MIT)
-Cấu trúc dữ liêu và giải thuật (Đỗ Xuân Lôi)

[songok]

Noi chung truoc khi tim chu trinh euler, ban phai dam bao no thoa man dieu kien chu trinh euler, : dieu kien nay kha phuc tap: vi du ta phai kiem tra khi do thi vo huong hay co huong, do thi co so dinh bac le hay bac chan.

[songok]

Co 1 thuat toan cung kha hieu qua de tim chu trinh euler hay duong euler nhung tui khong nho ro ten;
Thuat toan dai khai nhu sau : Gia su ta dang xe dinh A, ta xet cac dinh lan can voi dinh A vi du nhu B, C ,D . Lan luot bo di canh AB, roi tu B ta dung DFS hay BFS de tim duong di tu B-> A, neu khong co thi canh nay chac chan se co trong chu trinh