thêm 1 bài về tìm chu trình

English | Vietnamese

Rules

Main Forum

Portal

Member Listing

Statistics

Search

Reading Room
[Register]

Login [ | https ]

Forum Index

Thảo luận hệ điều hành Windows

thêm 1 bài về tìm chu trình

[Programming] thêm 1 bài về tìm chu trình	25/12/2009 23:02:50 (+0700) \| #1 \| 201870

longkt90
Member

Joined: 27/08/2009 20:44:22
Messages: 61
Offline

Hôm trước em có hỏi về chu trình nhỏ nhất, thấy mấy cái chu trinh cũng hay hay. Mong các bác giúp em câu nữa. smilie

Câu này cũng là ông thầy em hỏi, nhưng không cần nộp và chưa được giải.

Đề: cho đồ thị có hướng G = (V, E).
1> Kiểm tra đồ thị có chu trình (có tổng trọng số) âm không (chu trình có thể là 1 đỉnh có khuyên)? nếu có in ra 1 chu trình âm (bất kì), nếu không sang câu 2
2> Kiểm tra đồ thị có chu trình bằng 0 không? nếu có in ra 1 chu trình bằng 0 (bất kì), nếu không sang câu 3
3> in ra chu trình có trọng số nhỏ nhất.

em chưa nghĩ ra cách nào hay giải quyết câu 2,3
câu 1 (ông thầy gợi í chứ em chả nghĩ ra) : thêm 1 đỉnh giả nối tất cả các đỉnh còn lại bằng 1 cạnh có trọng số = 0 hướng từ đỉnh giả ra các đỉnh đó. Sau đó dùng bellman - ford trên đồ thị mới => có chu trình âm hay không, theo em khi đó có thể in ra chu trình bằng 0 bằng vài lệnh.
Vậy xong câu 1, con câu 2,3 smilie

Go to:

Users currently in here
1 Anonymous