tailieunhanh - 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. | 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 . Tổng quan về đồ thị . 1 . Định nghĩa đồ thị . 1 . Các thuật ngữ căn bản .4 . Một số dạng đồ thị . 6 . Biểu diễn đồ thị .9 . Biểu diễn bằng ma trận kề ma trận liên thuộc .9 . Danh sách cạnh cung của đồ thị .11 . 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 . Tìm kiếm theo chiều sâu trên đồ thị .17 . Tìm kiếm theo chiều rộng trên đồ thị .20 . Tìm đƣờng đi và kiểm tra tính liên thông . 21 . Tô màu đồ thị .28 . Giới thiệu .28 . Các khái niệm cơ bản .29 . Ví dụ .30 . Thuật toán .33 Bài tập . 33 CHƢƠNG 3 ĐỒ THỊ EULER VÀ ĐỒ THỊ HAMINTON .34 . Đồ thị Euler .34 . Khái niệm về đƣờng đi và chu trình Euler .34 . Điều kiện tồn tại đƣờng đi hoặc chu trình Euler .35 . Thuật toán tìm đƣờng đi và chu trình Euler .36 . Một số vấn đề khác về đƣờng đi và chu trình Euler .37 . Đồ thị Haminton .37 . Khái niệm về đƣờng đi và chu trình Haminton .38 . Điều kiện tồn tại đƣờng đi hoặc chu trình Haminton .38 . Thuật toán tìm đƣờng đi và chu trình Haminton .39 Bài tập . 40 . Khái niệm và các tính chất của cây khung . 43 . Cây khung của đồ thị . 44 . Xây dựng các tập chu trình cơ bản của đồ thị .47 . Cây khung nhỏ nhất của đồ thị .49 . Thuật toán Kruskal . 50 . Thuật toán Prim . 56 . Ứ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 . Các khái niệm mở đầu . 63 . Đƣờng đi ngắn nhất xuất phát từ một đỉnh . 65 . Thuật toán Dijkstra . 68 . Thuật toán Floyd-Washall .71 . Thuật toán Bellman-Ford .75 Bài tập . 80 CHƢƠNG 6 BÀI TOÁN LUỒNG C C ĐẠI .

• Kỹ thuật lập trình
• Bài giảng Lý thuyết đồ thị
• Lý thuyết đồ thị
• Phương pháp biểu diễn đồ thị
• Thuật toán tìm kiếm cơ bản
• Thuật toán tìm cây khung nhỏ nhất
• Bài toán luồng cực đại
• Giới thiệu Lý thuyết đồ thị
• Môn học Lý thuyết đồ thị
• Đại cương Lý thuyết đồ thị
• Hình thức thi Lý thuyết đồ thị
• Đại cương về đồ thị
• Các mô hình đồ thị
• Thuật ngữ cơ bản của đồ thị
• Đường đi của đồ thị
• Sự liên thông đồ thị
• tài liệu về lý thuyết đồ thị
• học lý thuyết đồ thị tốt
• phương pháp học lý thuyết đồ thị
• hàm trên đồ thị
• Đơn đồ thị đặc biệt
• Đồ thị bánh xe
• Đồ thị con
• Mô hình đồ thị
• Lịch sử của lý thuyết đồ thị
• Ưng dụng của đồ thị
• Tổng quan lý thuyết đồ thị
• Bài toán 7 cái cầu
• Biểu diễn đồ thị trên máy tính
• Sự đẳng cấu của đồ thị
• Biểu diễn đồ thị bằng ma trận kề
• Đồ thị Euler
• Đồ thị Hamilton
• Chu trình Hamilton
• Kiểm tra đồ thị Hamilton
• Đồ thị phẳng
• Bài toán tô màu đồ thị
• Công thức Euler
• Định lý Kuratowski
• Đồ thị không phẳng
• Tô màu đồ thị
• Bài toán lý thuyết đồ thi
• Bài toán lý thuyết đồ thị
• Bất đẳng thức EV
• Biểu diễn đồ thị
• Bậc của đỉnh
• Định nghĩa đồ thị
• Bài tập đồ thị
• Thuật toán tìm kiếm trên đồ thị
• Đồ thị Haminton
• Cây khung của đồ thị
• Đồ thị đẳng cấu
• Đồ thị tổng vành; Đồ thị đơn giản
• Đồ thị liên thông
• Dạng đồ thị đặc biệt
• Chu trình của đồ thị
• Chiều sâu trên đồ thị
• Chiều rộng trên đồ thị
• Tìm kiếm chiều rộng trên đồ thị
• Tìm kiếm trên đồ thị
• Đồ thị hữu hạn
• Đẳng cấu đồ thị
• Các dạng đồ thị
• Toán ứng dụng