Bài giảng Lý thuyết đồ thị - ĐH Hàng Hải VN

Giáo trình cung cấp cho người học những kiến thức thức về đồ thị, ứng dụng các bài toán tin học trên đồ thị: các phương pháp biểu diễn đồ thị, các thuật toán tìm kiếm cơ bản trên đồ thị, các chu trình và thuật toán tìm cây khung nhỏ nhất, các thuật toán tìm đường đi ngắn nhất, bài toán luồng cực đại. Mời các bạn cùng tham khảo để biết thêm những nội dung chi tiết.
Nội dung trích xuất từ tài liệu:
Bài giảng Lý thuyết đồ thị - ĐH Hàng Hải VN BỘ GIAO THÔNG VẬN TẢI TRƢỜNG ĐẠI HỌC HÀNG HẢI BỘ MÔN: KHOA HỌC MÁY TÍNH KHOA: CÔNG NGHỆ THÔNG TIN BÀI GIẢNG LÝ THUYẾT ĐỒ THỊ TÊN HỌC PHẦN : LÝ THUYẾT ĐỒ THỊ MÃ HỌC PHẦN : 17205 TRÌNH ĐỘ ĐÀO TẠO : ĐẠI HỌC CHÍNH QUY DÙNG CHO SV NGÀNH : CÔNG NGHỆ THÔNG TIN HẢI PHÒNG - 2009 MỤC LỤC CHƢƠNG 1: CÁC KHÁI NIỆM CƠ BẢN CỦA LÝ THUYẾT ĐỒ THỊ .....................1 1.1. Tổng quan về đồ thị .............................................................................................. 1 1.1.1. Định nghĩa đồ thị ........................................................................................... 1 1.1.2. Các thuật ngữ căn bản ...................................................................................4 1.1.3. Một số dạng đồ thị ......................................................................................... 6 1.2. Biểu diễn đồ thị ....................................................................................................9 1.2.1. Biểu diễn bằng ma trận kề, ma trận liên thuộc ..............................................9 1.2.2. Danh sách cạnh, cung của đồ thị .................................................................11 1.2.3. Danh sách kề ................................................................................................ 12 Bài tập ........................................................................................................................ 16 CHƢƠNG 2: CÁC THUẬT TOÁN TÌM KIẾM TRÊN ĐỒ THỊ ................................ 17 2.1. Tìm kiếm theo chiều sâu trên đồ thị ...................................................................17 2.2. Tìm kiếm theo chiều rộng trên đồ thị .................................................................20 2.3. Tìm đƣờng đi và kiểm tra tính liên thông ........................................................... 21 2.4. Tô màu đồ thị ......................................................................................................28 2.4.1. Giới thiệu ........................................................................................................28 2.4.2. Các khái niệm cơ bản ..................................................................................29 2.4.3. Ví dụ ............................................................................................................30 2.4.5. Thuật toán ....................................................................................................33 Bài tập ........................................................................................................................ 33 CHƢƠNG 3: ĐỒ THỊ EULER VÀ ĐỒ THỊ HAMINTON .........................................34 3.1. Đồ thị Euler ........................................................................................................34 3.1.1. Khái niệm về đƣờng đi và chu trình Euler ..................................................34 3.1.2. Điều kiện tồn tại đƣờng đi hoặc chu trình Euler .........................................35 3.1.3. Thuật toán tìm đƣờng đi và chu trình Euler ................................................36 3.1.4. Một số vấn đề khác về đƣờng đi và chu trình Euler ....................................37 3.2. Đồ thị Haminton .................................................................................................37 3.2.1. Khái niệm về đƣờng đi và chu trình Haminton ...........................................38 3.2.2. Điều kiện tồn tại đƣờng đi hoặc chu trình Haminton ..................................38 3.2.3. Thuật toán tìm đƣờng đi và chu trình Haminton .........................................39 Bài tập ........................................................................................................................ 40 4.1. Khái niệm và các tính chất của cây khung ......................................................... 43 4.2. Cây khung của đồ thị .......................................................................................... 44 4.3. Xây dựng các tập chu trình cơ bản của đồ thị ....................................................47 4.4. Cây khung nhỏ nhất của đồ thị ...........................................................................49 4.4.1. Thuật toán Kruskal ...................................................................................... 50 4.4.2. Thuật toán Prim ........................................................................................... 56 4.4.3. Ứng dụng của bài toán tìm cây khung nhỏ nhất ..........................................59 Bài tập ........................................................................................................................ 60 CHƢƠNG 5: BÀI TOÁN ĐƢ NG ĐI NGẮN NHẤT ................................................63 5.1. Các khái niệm mở đầu ........................................................................................ 63 5.2. Đƣờng đi ngắn nhất xuất phát từ một đỉnh ......................................................... 65 5.3. Thuật toán Dijkstra ............................................................................................. 68 5.4. Thuật toán Floyd-Washall ..................................................................................71 5.5. Thuật toán Bellman-Ford ...................................................................................75 Bài tập ........................................................................................................................ 80 CHƢƠNG 6: BÀI TOÁN LUỒNG C C ĐẠI TRONG MẠNG .................................83 6.1. Mạng. Luồng trong mạng. Bài toán luồng cực đại ......................... ...