Trong tài liệu này sẽ cho bạn những kiến thức về đồ cơ bản về thuyết đồ thị trong thị, bổ sung thêm cho bạn nhưng kiến thức quan trọng về đồ thị để cho bạn thêm logic phát triển ứng dụng sau này. | CÁC BAI TOÁN ĐƯỜNG ĐI 1 Bài toán đường đi ngắn nhất Phát biểu bài toan Cho G X E là một đồ thị co hướng. Ta định nghĩa ánh xa trong lướng như sau L E----- IR e I--- L e xet hai đỉnh i j eX gội P la một đướng đi từ đỉnh i đến đỉnh j trong lướng hay gia cua đướng đi P đước định nghĩa là L P Z eep L e Lý thuyết Đổ thj - Các bài toán đường đi - Khoa CNTT - Đại hoc KHTN 3 Bài toàn đường đi ngàn nhá t Muc đích cua bai toan đướng đi ngan nhai la tìm đướng đi P từ i đen j co trong lương nho nhai trong so tat ca những đướng đi co the co. z-x 8 8 7 k2 3 B D 2 F 5 Lý thuyết Đổ thj - Các bái toán đường đi - Khoa CNTT - Đại hoc KHTN 4 2 Bài toan đường đi ngắn nhất Nhận xét Mặc dù bài toán được phát biểu cho đồ thị co hướng co trong nhưng các thuặt toán sể trình bày đểu cồ thể áp dung cho các đo thị vo hướng co trong báng cách xem moi cánh củá đo thị vo hướng như hái cánh co cung trong lượng nôi cung một cáp đỉnh nhưng co chiểu ngược nháu. Lý thuyết Đổ thj - Các bài toán đường đi - Khoa CNTT - Đại hoc KHTN 5 Bài toan đường đi ngắn nhất Nhận xét Khi lám bái toán tìm đướng đi ngán nhất chung tá co thể bo bớt đi các cánh song song vá chỉ chừá lái mọt cánh co trong lướng nho nhất trong so các cánh song ._pj song. Đối với các khuyên co trong lướng khong ám thì cung co thể bo đi má khong lám ánh hướng đến kết quá cuá bái toán. Đoi với các khuyển co trong lướng ám thì co thể đưá đến bái toán đướng đi ngán nhất khong co lới giái Lý thuyết Đồ thi - Các bài toán đường đi - Khoa CNTT - Đại học KHTN 6
