Tiểu Luận Cây phủ nhỏ nhất và ứng dụng

MỤC LỤC
Trang
MỞ ĐẦU 3
CHƯƠNG I. ĐẠI CƯƠNG VỀ ĐỒ THỊ. 4
I. Một số khái niệm . 4
1. Đồ thị có hướng và đồ thị vô hướng. 4
2. Đường đi, chu trình, tính liên thông. 4
3. Trọng đồ. 5
4. Đồ thị con. 6
5. Biểu diễn đồ thị 6
II. Cây và cây phủ. 9
1. Cây. 9
2. Cây phủ. 11
3. Khái niệm cây phủ nhỏ nhất. 11
CHƯƠNG II. CÂY PHỦ NHỎ NHẤT 12
I. Bài toán cây phủ nhỏ nhất. 12
1. Bài toán thực tế. 12
2. Bài toán tổng quát. 12
3. Định lý. 12
II. Các thuật toán tìm cây phủ nhỏ nhất. 13
1. Thuật toán Prim . 13
2. Thuật toán Kruskal 17
III. Đánh giá thuật toán Kruskal và thuật toán Prim . 20
CHƯƠNG III. ỨNG DỤNG 21
I. Giải các toán thực tế. 21
II. Bài toán cây phủ nhỏ nhất. 21
III. Bài toán tìm mạng điện với độ tin cậy lớn nhất. 22
KẾT LUẬN 23
TÀI LIỆU THAM KHẢO 24




MỞ ĐẦU

Lý thuyết đồ thị là ngành khoa học được phát triển từ lâu nhưng lại có nhiều ứng dụng hiện đại. Đồ thị là một cấu trúc rời rạc gồm các đỉnh và các cạnh nối các đỉnh đó. Đây là công cụ hữu hiệu để mô hình hoá và giải quyết các bài toán trong nhiều lĩnh vực khoa học, kỹ thuật, kinh tế, xã hội

Khi nghiên cứu bộ môn lý thuyết đồ thị, chúng ta được tiếp cận với nhiều khái niệm, tri thức mới. Trong đó, một khái niệm mà chúng ta không thể không nhắc tới đó là khái niệm về CÂY. Cây là một cấu trúc dữ liệu được sử dụng rộng rãi gồm một tập hợp các đỉnh (nút). Một trong số những bài toán liên quan đến cây mà chúng ta được tìm hiểu đó là bài toán tìm cây phủ (cây bao trùm). Đồ thị có cây phủ là đồ thị khi ta chọn một đỉnh làm đỉnh gốc thì qua đỉnh đó luôn có một đường đi đi qua tất cả các đỉnh còn lại của đồ thị. Cây phủ thì có nhiều ứng dụng trong các bài toán điều khiển giao thông, nối các mạng điện Ngoài ra, chúng ta còn sử dụng khái niệm cây phủ để kiểm tra tính liên thông của một đồ thị.
Trong thực tế có một vấn đề đặt ra là: Khi ta xây dựng các con đường thông thương giữa các thành phố, làm thế nào để chi phí bỏ ra là thấp nhất nếu ta biết trước được chi phí của con đường giữa 2 thành phố bất kỳ. Từ yêu cầu thực tế này dẫn đến bài toán “Tìm cây phủ nhỏ nhất”.
Bài toán tìm cây phủ nhỏ nhất (hay cây khung tối tiểu- Minimmum Spanning Tree - MST) của một đồ thị vô hướng là một bài toán rất nổi tiếng và có ứng dụng rất lớn. Hiện nay đã có rất nhiều thuật toán giải quyết bài toán MST trong các trường hợp cụ thể để giải quyết các bài toán thực tế. Tuy nhiên hai giải thuật kinh điển để tìm cây phủ nhỏ nhất là thuật toán Prim và thuật toán Kruska