[Giáo trình Toán rời rạc] - Chương4 - Đồ thị Euler & Hamilton potx

... 1) ðồ thị có một chu trình vừa là chu trình Euler vừa là chu trình Hamilton; 2) ðồ thị có một chu trình Euler và một chu trình Hamilton, nhưng hai chu trình ñó không trùng nhau; 3) ðồ thị có ... yếu ñối với ñồ thị có hướng) có chứa một chu trình (t.ư. ñường ñi) Euler ñược gọi là ñồ thị Euler (t.ư. nửa Euler) . Thí dụ 1: ðồ thị không nửa E...

Ngày tải lên: 01/07/2014, 17:20

... ñồ thị con liên thông, mỗi cặp các ñồ thị con này không có ñỉnh chung. Các ñồ thị con liên thông rời nhau như vậy ñược gọi là các thành phần liên thông của ñồ thị ñang xét. Như vậy, một ñồ thị ... thế kỷ 18 bởi nhà toán học Thụy Sĩ tên là Leonhard Euler. Ông ñã dùng ñồ thị ñể giải quyết bài toán 7 chiếc cầu Konigsberg nổi tiếng. ðồ thị cũng ñược dùng ñể giải các bài...

Ngày tải lên: 01/07/2014, 17:20

... thuật toán Floyd vào đồ thị sau: 6. Giải bài toán mạng vận tải sau bằng thuật toán Ford-Fulkerson với luồng vận tải khởi đầu bằng 0. 7. Giải bài toán mạng vận tải sau bằng thuật toán Ford-Fulkerson ... , v k-1 } và W k-1 [i,k]+W k-1 [k,j] = chiều dài(v 1 v k ) + chiều dài(v k v j ) = chiều dài γ < W k-1 [i,j]. Do đó theo định nghĩa của W k thì ta có: W k [i,j] = W k-1 [...

Ngày tải lên: 26/08/2013, 20:26

... , u n } thì: 0 = d(u 0 ,u 0 ) < d(u 0 ,u 1 ) < d(u 0 ,u 2 ) < < d(u 0 ,u n ). 5.1.3. Thuật toán Dijkstra: procedure Dijkstra (G=(V,E) là đơn đồ thị liên thông, có trọng số với ... v k-1 } và W k-1 [i,k]+W k-1 [k,j] = chiều dài(v 1 v k ) + chiều dài(v k v j ) = chiều dài γ < W k-1 [i,j]. Do đó theo định nghĩa của W k thì ta có: W k [i,j] = W k-1 [i,k]+W k-1 [k...

Ngày tải lên: 11/12/2013, 16:15