tailieunhanh - Bài giảng Toán rời rạc và lý thuyết đồ thị - Chương 6: Cây và cây khung của đồ thị

Chương 6 cung cấp cho người học những kiến thức về cây và cây khung của đồ thị. Chương này giúp người học có những hiểu biết về cây và các tính chất cơ bản của cây, cây khung của đồ thị, bài toán tìm cây khung nhỏ nhất. để nắm bắt các nội dung chi tiết. | Chương 6. Cây và cây khung của đô thị 1. CÀY VÀ CÁC TÍNH CHẤT CƠ BẢN CỦA CÀY Định nghĩal. Ta gọi cây là đồ thị vô hướng liên thông không có chu trình. Đồ thị không có chu trình được gọi là rừng. Như vậy rừng là đồ thị mà mỗi thành phần liên thông của nó là một cây. Thí dụ 1. Trong hình 1 là một rừng gồm 3 cây T1 T2 T3. Hình 1. Rừng gồm 3 cây T1 T2 T3. Có thể nói cây là đồ thị vô hướng đơn giản nhất. Định lý sau đây cho ta một số tính chất của cây. Định lý 1. Giả sử G V E là đồ thị vô hướng n đỉnh. Khi đó các mệnh đề sau đây là tương đương 1 T là cây 2 T không chứa chu trình và có n-1 cạnh 3 T liên thông và có n-1 cạnh 4 T liên thông và mỗi cạnh của nó đều là cầu 5 Hai đỉnh bất kỳ của T được nối với nhau bởi đúng một đường đi đơn 6 T không chứa chu trình nhưng hễ cứ thêm vào một cạnh ta thu được đúng một chu trình. 2. CÀY KHUNG CỦA ĐỒ THỊ Định nghĩa 2. Cho đồ thị vô hướng liên thông G V E cây khung T Vt Et của nó được xác định như sau Tập đỉnh của cây T cũng là tập đỉnh của đồ thị G. tức là VT V. Tập cạnh của cây T là tập con của tập cạnh của đồ thị G. tức là ET c V. Nói cách khác từ đồ thị G ta bỏ bớt các cạnh đi cho thành 1 cây thì đó là một cây khung của đồ thị. Như vậy 1 đồ thị có thể có nhiều cây khung. Ví dụ Hình 2. Đồ thị và 2 các cây khung của nó nó còn có các cây khung khác 3. BÀI TOÁN TÌM CÀY KHUNG NHỎ NHẤT. Bài toán cây khung nhỏ nhất của đồ thị là một trong số những bài toán tối ưu trên đồ thị tìm được ứng dụng trong nhiều lĩnh vực khác nhau của đời sống. Trong mục này chúng ta trình bày những thuật toán cơ bản để giải bài toán này. Trước hết chúng ta phát biểu nội dung bài toán. Cho G V E là đồ thị vô hướng liên thông. Mỗi cạnh e của đồ thị G được gán với một trọng số không âm c e gọi là độ dài của nó. Giả sử T Vt Et là cây khung của đồ thị G. Ta gọi độ dài c T của cây khung T là tổng độ dài các cạnh của nó c T s c e . ee Et Bài toán đặt ra là trong tất cả cây khung của đồ thị G hãy tìm cây khung với độ dài nhỏ nhất. Cây khung như vậy như vậy được gọi .

• Toán học
• Toán rời rạc
• Lý thuyết đồ thị
• Cây khung của đồ thị
• Đồ thị vô hướng
• Cây khung nhỏ nhất
• Đồ thị G
• Bài giảng toán rời rạc
• Giáo trình toán rời rạc
• Tài liệu toán rời rạc
• Học toán rời rạc
• Lý thuyết về toán rời rạc
• Bài tập về toán rời rạc
• Ôn tập toán rời rạc
• Đề thi toán rời rạc