First topic message reminder :

Già Làng đã viết:

ĐỀ THI MÔN LÍ THUYẾT ĐỒ THỊ

1. Liệt kê tất cả các phép toán trên đồ thị
2. Dùng phương pháp cm phản chứng để cmr: nếu n lẻ thì n2 lẻ
3. Quy nạp là gì? Vì sao phải sử dụng phương pháp quy nạp
4. Trình bày thuật ngữ đệ quy
5. Trình bày phương pháp quy nạp dạng mạnh
6. Trình bày phương pháp quy nạp dạng yếu
7. Trình bày phương pháp chứng minh trực tiếp
8. Quan hệ, hàm, phương trình, ánh xạ, công thức có tương đương hay không?
9. Lặp, đệ quy, quy nạp là tương đương nhau đương nhau đúng hay không?
10. Cm:căn bậc 2 không phải là số vô tỉ bằng pp phản chứng
11. Chạy bằng tay chu trình Euler
12. Hãy nêu cơ sở hình thành nguyên lý tối ưu
13. Vì sao thuật toán Dijikstra lại đưa ra dk không có trọng số âm,vì thuật toán Bellman Ford lại đưa ra đk không có chu trình âm.
14. Chạy bằng tay thuật toán Dijikstra.

Các bạn nào đã từng làm những câu hỏi này thì post lên cho anh em tham khảo nha!
Thân!

Câu 13: Bellman Ford lại đưa ra đk không có chu trình âm? đơn giản là nó đòi hỏi trọng số của các cung phải có giá trị không âm. hehe! OK ko các bạn!

Câu 13, Dijkstra lại yêu cầu trọng số không âm?
Chúng ta dùng các đỉnh của đồ thị để mô hình các thành phố và các cạnh để mô hình các đường nối giữa chúng. Khi đó trọng số các cạnh có thể xem như độ dài của các con đường (và do đó là không âm). Chúng ta cần vận chuyển từ thành phố s đến thành phố t. Thuật toán Dijkstra sẽ giúp chỉ ra đường đi ngắn nhất chúng ta có thể đi.
Trọng số không âm của các cạnh của đồ thị mang tính tổng quát hơn khoảng cách hình học giữa hai đỉnh đầu mút của chúng. Ví dụ, với 3 đỉnh A, B, C đường đi A-B-C có thể ngắn hơn so với đường đi trực tiếp A-C.

mấy U mới thi có 2 môn mà đuối rồi hay sao mà ko thấy ai thảo luận hết vậy trời!?????????

cái này còn câu này nữa cho nó là câu 15 nha : tính độ phức tạp của thuật toán Dijistra và Bellman. Cho biết sự phức tạp của 2 thuật toán.

Thuật toán Bellman-Ford lá 1 thuật toán tính đường đi ngắn nhất trong 1 đồ thị có hướng có trọng số!
_Thuật toán không có chu trình âm Vì nếu tồn tại chu trình âm mà từ đỉnh nguồn có thể đi đến được thì sẽ không tồn tại đường đi nhỏ nhất(vì mỗi lần đi quanh chu trình âm là 1 lần giảm trọng số của đường)
(sưu tầm @_@)

bubupro.gdty đã viết:

cái này còn câu này nữa cho nó là câu 15 nha : tính độ phức tạp của thuật toán Dijistra và Bellman. Cho biết sự phức tạp của 2 thuật toán.

cái này chắc ko dzô đâu? nó nằm bên môn kiùi! kkaaka