THUẬT TOÁN TÌM LÁT CẮT HẸP NHẤT

 TRÊN ĐỒ THỊ VÔ HƯỚNG CÓ TRỌNG SỐ 

Trích:

Đồ án Phân tích và thiết kế thuật toán

Giảng viên hướng dẫn: PGS. TS. VŨ THANH NGUYÊN

Sinh viên thực hiện:

NGUYỄN TRÍ HẢI, MSSV: 11520094

NGUYỄN HOÀNG NGHĨA, MSSV: 11520603

ĐẠI HỌC QUỐC GIA TP. HỒ CHÍ MINH

TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN

KHOA KHOA HỌC MÁY TÍNH

Những khái niệm cơ bản về lý thuyết đồ thị được đã được nhà toán học Thuỵ Sĩ Leonhard Euler đưa ra từ thế kỷ thứ XVIII từ bài toán nổi tiếng về cây cầu Konigsberg. Mặc dù lý thuyết đồ thị đã được khoa học phát triển từ rất lâu nhưng có nhiều ứng dụng hiện đại khi mà máy tính điện tử ra đời và sự phát triển của tin học.

        Tính liên thông của đồ thị là một trong những vấn đề cơ bản của các thuật toán về đồ thị và có rất nhiều ứng dụng thực tế. Bài toán tìm lát cắt nhỏ nhất của đồ thị liên thông có trọng số là một trong những bài toán cơ bản. Thuật toán để giải quyết bài toán này cho ta kết quả một cách chia tập đỉnh hiện tại thành hai tập con sao cho trọng số của các cạnh nối giữa hai tập là nhỏ nhất.

Link download Report & Demo: