TAILIEUCHUNG - Bài giảng lý thuyết đồ thị - Chương 6

MỘT SỐ BÀI TOÁN ỨNG DỤNG (Bài toán tìm đường đi ngắn nhất và bài toán luồng cực đại) Bài toán tìm đường đi ngắn nhất Tìm đường đi ngắn nhất trong đồ thị không có trọng số Bài toán: Cho đồ thị không có trọng số G = (V,E) và hai đỉnh u, v ∈ V. | Giáo án môn Lý Thuyết Đô Thị Chương 6 MỘT SỐ BÀI TOÁN ỨNG DỤNG Bài toán tìm đường đi ngắn nhất và bài toán luồng cực đại Bài toán tìm đường đi ngắn nhất Tìm đường đi ngắn nhất trong đồ thị không có trọng số Bài toán Cho đồ thị không có trọng số G V E và hai đỉnh u v e V. Tìm đường đi ngắn nhất từ đỉnh u đến đỉnh v tức là đường đi từ u đến v có số cạnh cung là ít nhất Để giải quyết bài toán này ta có thể thực hiện theo thuật toán sau đây Thuât toán Bước 1 Tại đỉnh u ta ghi số 0 Các đỉnh kề với u có cạnh đi từ u đến ta ghi số 1 Các đỉnh kề với các đỉnh đã được ghi số 1 ta ghi số 2 Giả sử ta đã ghi tới i tức là ta đã đánh số được các tập đỉnh là V 0 u V 1 V 2 . V i . Trong đó V i là tập tất cả các đỉnh được ghi bởi số i. Ta xác định tập các đỉnh được đánh số bởi số i 1 như sau V i 1 x x e V xỂ V k với k 0 1 . i và 3 ye V i sao cho từ y có cạnh cung đi tưới x Do tính hữu hạn của đồ thị sau một số hữu hạn bước thuật toán dừng lại và cho ta tập các đỉnh có chứa đỉnh v được đánh số bởi m là V m . Bước 2 Do ở bước 1 đỉnh v được đánh số là m điều này chứng tỏ đường đi từ u đến v có m cạnh cung và là đường đi ngắn nhất từ u tới v. Để tìm tất cả các đường đi có độ dài m ngắn nhất từ u tới v ta xuất phát từ v đi ngược về u theo nguyên tắc sau đây - Tìm tất cả các đỉnh có cạnh cung tới b được ghi số m-1 giả sử đó là xik k 1 2. . - Với mỗi đỉnh xik tìm tất cả các đỉnh có cạnh cung tới xik được ghi số m-2. Bằng cách lùi dần trở lại đến một lúc nào đó gặp đỉnh ghi số 0 đó chính là đỉnh u. Tất cả các đường đi xác đinh theo các bước trên là đường đi từ u tới v với độ dài m ngắn nhất cần tìm Ví dụ Xét đồ thị có hướng cho bởi hình dưới đây Hình Tìm đường đi ngắn nhất từ đỉnh v1 đế 60 Nguyễn Minh Đức - ĐHQG Hà Nội Giáo án môn Lý Thuyết Đô Thị Chu ý Thuật toán tìm đường đi giữa hai đỉnh u và v trong đồ thị bằng cách áp dụng thuật toán tìm kiếm theo chiều rộng chính là đường đi ngắn nhất từ u tới v theo số cạnh . Tìm đường đi ngắn nhất trong đồ thị có trọng số Bài .

• Toán học
• biểu diễn đồ thị
• thuật toán
• đồ thị euler
• phương pháp biểu diễn
• cây khung
• Lý thuyết đồ thị
• Bài giảng Lý thuyết đồ 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ề
• Bài giảng Toán rời rạc 2
• Toán rời rạc 2
• Toán rời rạc
• Biểu diễn đồ thị bằng danh sách kề
• Ma trận liên thuộc
• Phân tích thiết kế giải thuật
• Bài giảng Phân tích thiết kế giải thuật
• Giải thuật tìm kiếm trong đồ thị
• Biểu diễn của một đồ thị
• Biểu diễn một đồ thị vô hướng
• Biểu diễn một đồ thị có hướng
• biểu diễn hình học
• biêu diễn đồ thị bằng ma trận
• biểu diễn đồ thị bằng bảng
• sự đẳng cấu của các đồ thị
• Số cạnh của đồ thị
• Cách biểu diễn đồ thị
• Ma trận trọng số
• Bài toán trên đồ thị
• Gom cụm đồ thị
• Khối thông điệp
• Diễn đàn thảo luận
• Bài toán gom cụm phẳng
• Biểu diễn văn bản bằng đồ thị
• Gom cụm đồ thị bằng mạng Kohonen
• tài liệu về đồ thị
• bậc của đỉnh trong đồ thị
• đại cương đồ thị
• bài giảng về đồ thị
• Bài giảng Toán rời rạc
• Đồ thị liên thông
• Biểu diễn đồ thị bằng ma trận
• Bài toán đường đi ngắn nhất
• Tiếp cận kết thúc mở
• Biểu diễn trực quan
• Biểu diễn đồ thị hàm số
• Hàm bậc hai
• Tính chất của dãy số
• Dạy học toán
• Khái niệm đồ thị
• đồ thị con
• đồ thị riêng
• sự đẳng hình của đồ thị
• định nghĩa đồ thị
• tô màu đồ thị
• Vẽ đồ thị
• Đồ thị phẳng
• bài toán luồng trên mạng
• tài liệu lý thuyết đồ thị
• đồ thị có hướng
• đồ thị hữu hạn
• đồ thị vô hạn
• Tìm kiếm trên đồ thị
• Đồ thị Hamilton
• Thuật toán đồ thị
• Ứng dụng tìm kiếm trên đồ thị
• Bài toán cây khung nhỏ nhất
• Thuật toán duyệt đồ thị