Tiểu Luận Thuật toán trên đồ thị (Tiểu luận môn phân tích thuật toán)

CÁC THUẬT TOÁN ĐỒ THỊ​
Đồ thị là một mô hình toán học được sử dụng để biểu diễn một tập đối
tượng có quan hệ với nhau theo một cách nào đó. Chẳng hạn trong khoa học
máy tính, đồ thị được sử dụng để mô hình hoá một mạng truyền thông, kiến
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
như công nghệ điện, hoá học, chính trị, kinh tế, . cũng có thể biểu diễn bởi
đồ thị. Khi một vấn đề được mô hình hoá bởi đồ thị, thì vấn đề sẽ được giải
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 đồ
thị có phạm vi áp dụng rộng lớn và có tầm quan trọng đặc biệt. Trong
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
đồ thị: các thuật toán đi qua đồ thị, các thuật toán tìm đường đi ngắn nhất,
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
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
trong chương 16) để giải quyết các vấn đề cụ thể.