TAILIEUCHUNG - Bài giảng Lý thuyết đồ thị: Chương 3 - Nguyễn Thanh Sơn

Chương 3 - Các bài toán đường đi. Những nội dung chính được trình bày trong chương này gồm có: Đường đi ngắn nhất: Bài toán, nguyên lý Bellman, thuật toán Dijkstra, thuật toán Floyd, thuật toán Ford-Bellman, đồ thị Euler; đồ thị Euler; đồ thị Hamilton. . | CÁC BÀI TOÁN ĐƯỜNG ĐI ntsonptnk@ NỘI DUNG Đường đi ngắn nhất Bài toán Nguyên lý Bellman Thuật toán Dijkstra Thuật toán Floyd Thuật toán Ford-Bellman Đồ thị Euler Đồ thị Hamilton Lý thuyết đồ thị , chương 3 - Nguyễn Thanh Sơn ĐƯỜNG ĐI NGẮN NHẤT Lý thuyết đồ thị - chương 3 - Nguyễn Thanh Sơn C B A E D F 0 3 2 8 5 8 4 8 7 1 2 5 2 3 9 Cho đồ thị có hướng có trọng G=(X, E) và hai đỉnh s, t X, gọi P là một đường đi từ đỉnh s đến đỉnh t, trọng lượng (hay giá) của đường đi P được định nghĩa là: L(P) = (e P)L(e) Bài toán: tìm đường đi từ s đến t có trọng lượng nhỏ nhất BÀI TOÁN Lý thuyết đồ thị - Nguyễn Thanh Sơn Bài toán được phát biểu cho đồ thị có hướng có trọng, nhưng các thuật toán sẽ trình bày đều có thể áp dụng cho các đồ thị vô hướng có trọng bằng cách xem mỗi cạnh của đồ thị vô hướng như hai cạnh có cùng trọng lượng nối cùng một cặp đỉnh nhưng có chiều ngược nhau. Khi tìm đường đi ngắn nhất có thể bỏ bớt đi các cạnh song song và chỉ chừa lại một cạnh có trọng .

• Kỹ thuật lập trình
• Lý thuyết đồ thị
• Bài giảng Lý thuyết đồ thị
• Các bài toán đường đi
• Đường đi ngắn nhất
• Đồ thị Euler
• Đồ thị Hamilton
• 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ị
• 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ị
• Đạ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ị
• Biểu diễn đồ thị trên máy tính
• Sự đẳng cấu của đồ thị
• Phương pháp biểu diễn đồ thị
• Biểu diễn đồ thị bằng ma trận kề
• Chu trình Hamilton
• Kiểm tra đồ thị Hamilton
• Đơn đồ thị đặc biệt
• Đồ thị bánh xe
• Đồ thị con
• Mô hình đồ thị