//
you're reading...
01 - Chủ đề thuật toán, Dùng cho thi học sinh giỏi, Giáo trình chuyên Tin học 10, Giáo trình Giải thuật và lập trình (LMH)

Giải thuật và lập trình – Phần 4 – Các thuật toán trên đồ thị

PHẦN 4. CÁC THUẬT TOÁN TRÊN ĐỒ THỊ 177
§1. CÁC KHÁI NIỆM CƠ BẢN 178
1.1. ĐỊNH NGHĨA ĐỒ THỊ (GRAPH) 178
1.2. CÁC KHÁI NIỆM 179
§2. BIỂU DIỄN ĐỒ THỊ TRÊN MÁY TÍNH 181
2.1. MA TRẬN KỀ (ADJACENCY MATRIX) 181
2.2. DANH SÁCH CẠNH (EDGE LIST) 182
2.3. DANH SÁCH KỀ (ADJACENCY LIST) 183
2.4. NHẬN XÉT 184
§3. CÁC THUẬT TOÁN TÌM KIẾM TRÊN ĐỒ THỊ 186
3.1. BÀI TOÁN 186
3.2. THUẬT TOÁN TÌM KIẾM THEO CHIỀU SÂU (DEPTH FIRST SEARCH) 187
3.3. THUẬT TOÁN TÌM KIẾM THEO CHIỀU RỘNG (BREADTH FIRST SEARCH) 189
3.4. ĐỘ PHỨC TẠP TÍNH TOÁN CỦA BFS VÀ DFS 192
§4. TÍNH LIÊN THÔNG CỦA ĐỒ THỊ 193
4.1. ĐỊNH NGHĨA 193
4.2. TÍNH LIÊN THÔNG TRONG ĐỒ THỊ VÔ HƯỚNG 194
4.3. ĐỒ THỊ ĐẦY ĐỦ VÀ THUẬT TOÁN WARSHALL 194
4.4. CÁC THÀNH PHẦN LIÊN THÔNG MẠNH 197
§5. VÀI ỨNG DỤNG CỦA DFS và BFS 208
5.1. XÂY DỰNG CÂY KHUNG CỦA ĐỒ THỊ 208
5.2. TẬP CÁC CHU TRÌNH CƠ SỞ CỦA ĐỒ THỊ 211
5.3. BÀI TOÁN ĐỊNH CHIỀU ĐỒ THỊ 211
5.4. LIỆT KÊ CÁC KHỚP VÀ CẦU CỦA ĐỒ THỊ 215
§6. CHU TRÌNH EULER, ĐƯỜNG ĐI EULER, ĐỒ THỊ EULER 219
6.1. BÀI TOÁN 7 CÁI CẦU 219
6.2. ĐỊNH NGHĨA 219
6.3. ĐỊNH LÝ 219
6.4. THUẬT TOÁN FLEURY TÌM CHU TRÌNH EULER 220
6.5. CÀI ĐẶT 221
6.6. THUẬT TOÁN TỐT HƠN 223
§7. CHU TRÌNH HAMILTON, ĐƯỜNG ĐI HAMILTON, ĐỒ THỊ HAMILTON 226
7.1. ĐỊNH NGHĨA 226
7.2. ĐỊNH LÝ 226
7.3. CÀI ĐẶT 227
§8. BÀI TOÁN ĐƯỜNG ĐI NGẮN NHẤT 231
8.1. ĐỒ THỊ CÓ TRỌNG SỐ 231
8.2. BÀI TOÁN ĐƯỜNG ĐI NGẮN NHẤT 231
8.3. TRƯỜNG HỢP ĐỒ THỊ KHÔNG CÓ CHU TRÌNH ÂM – THUẬT TOÁN FORD BELLMAN 233
8.4. TRƯỜNG HỢP TRỌNG SỐ TRÊN CÁC CUNG KHÔNG ÂM – THUẬT TOÁN DIJKSTRA 235
8.5. THUẬT TOÁN DIJKSTRA VÀ CẤU TRÚC HEAP 238
8.6. TRƯỜNG HỢP ĐỒ THỊ KHÔNG CÓ CHU TRÌNH – SẮP XẾP TÔ PÔ 241
8.7. ĐƯỜNG ĐI NGẮN NHẤT GIỮA MỌI CẶP ĐỈNH – THUẬT TOÁN FLOYD 244
8.8. NHẬN XÉT 246
§9. BÀI TOÁN CÂY KHUNG NHỎ NHẤT 251
9.1. BÀI TOÁN CÂY KHUNG NHỎ NHẤT 251
9.2. THUẬT TOÁN KRUSKAL (JOSEPH KRUSKAL – 1956) 251
9.3. THUẬT TOÁN PRIM (ROBERT PRIM – 1957) 256
§10. BÀI TOÁN LUỒNG CỰC ĐẠI TRÊN MẠNG 260
10.1. CÁC KHÁI NIỆM 260
10.2. MẠNG THẶNG DƯ VÀ ĐƯỜNG TĂNG LUỒNG 263
10.3. THUẬT TOÁN FORD-FULKERSON (L.R.FORD & D.R.FULKERSON – 1962) 266
10.4. THUẬT TOÁN PREFLOW-PUSH (GOLDBERG – 1986) 270
10.5. MỘT SỐ MỞ RỘNG 276
§11. BÀI TOÁN TÌM BỘ GHÉP CỰC ĐẠI TRÊN ĐỒ THỊ HAI PHÍA 283
11.1. ĐỒ THỊ HAI PHÍA (BIPARTITE GRAPH) 283
11.2. BÀI TOÁN GHÉP ĐÔI KHÔNG TRỌNG VÀ CÁC KHÁI NIỆM 283
11.3. THUẬT TOÁN ĐƯỜNG MỞ 284
11.4. CÀI ĐẶT 285
§12. BÀI TOÁN TÌM BỘ GHÉP CỰC ĐẠI VỚI TRỌNG SỐ CỰC TIỂU TRÊN ĐỒ THỊ HAI PHÍA – THUẬT TOÁN HUNGARI 291
12.1. BÀI TOÁN PHÂN CÔNG 291
12.2. PHÂN TÍCH 291
12.3. THUẬT TOÁN 292
12.4. BÀI TOÁN TÌM BỘ GHÉP CỰC ĐẠI VỚI TRỌNG SỐ CỰC ĐẠI TRÊN ĐỒ THỊ HAI PHÍA 301
12.5. NÂNG CẤP 301
§13. BÀI TOÁN TÌM BỘ GHÉP CỰC ĐẠI TRÊN ĐỒ THỊ 307
13.1. CÁC KHÁI NIỆM 307
13.2. THUẬT TOÁN EDMONDS (1965) 308
13.3. THUẬT TOÁN LAWLER (1973) 310
13.4. CÀI ĐẶT 312
13.5. ĐỘ PHỨC TẠP TÍNH TOÁN 316

About pascalteacher

Trang thông tin Toán học và Tin học

Thảo luận

Chưa có phản hồi.

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s

Các tác giả

Danh mục

Tháng Mười 2016
M T W T F S S
« Sep   Nov »
 12
3456789
10111213141516
17181920212223
24252627282930
31  

NCT Computer

Flickr Photos

Clouds and sky

Toss-up

Winter Sunrise

More Photos

Thống kê

  • 95,640 lượt xem

pascalteacher.nct@gmail.com


Trang huấn luyện học sinh giỏi Tin học

%d bloggers like this: