[FONT=Times New Roman]CÁC THUẬT TOÁN ĐỒ THỊ

[FONT=Times New Roman]Đồ thị là một mô hình toán học được sử dụng để biểu diễn một tập đối

[FONT=Times New Roman]tượng có quan hệ với nhau theo một cách nào đó. Chẳng hạn trong khoa học

[FONT=Times New Roman]máy tính, đồ thị được sử dụng để mô hình hoá một mạng truyền thông, kiến

[FONT=Times New Roman]trúc của các máy tính song song, . Rất nhiều vấn đề trong các lĩnh vực khác

[FONT=Times New Roman]như công nghệ điện, hoá học, chính trị, kinh tế, . cũng có thể biểu diễn bởi

[FONT=Times New Roman]đồ thị. Khi một vấn đề được mô hình hoá bởi đồ thị, thì vấn đề sẽ được giải

[FONT=Times New Roman]quyết bằng cách sử dụng các thuật toán trên đồ thị. Vì vậy các thuật toán đồ

[FONT=Times New Roman]thị có phạm vi áp dụng rộng lớn và có tầm quan trọng đặc biệt. Trong

[FONT=Times New Roman]chương này chúng ta sẽ nghiên cứu một số thuật toán quan trọng nhất trên

[FONT=Times New Roman]đồ thị: các thuật toán đi qua đồ thị, các thuật toán tìm đường đi ngắn nhất,

[FONT=Times New Roman]tìm cây bao trùm ngắn nhất . Nghiên cứu các thuật toán đồ thị còn giúp ta

[FONT=Times New Roman]hiểu rõ hơn cách vận dụng các kỹ thuật thiết kế thuật toán (đã được trình bày

[FONT=Times New Roman]trong chương 16) để giải quyết các vấn đề cụ thể