TAILIEUCHUNG - Bài giảng Lý thuyết đồ thị: Chương 4 - Ngô Hữu Phúc

"Bài giảng Lý thuyết đồ thị - Chương 4: Cây và cây khung của đồ thị" với các nội dung định nghĩa và các tính chất cơ bản, cây khung và bài toán tìm cây khung nhỏ nhất, thuật toán Kruskal, thuật toán Prim, cây có gốc. | CHƯƠNG IV CÂY VÀ CÂY KHUNG CỦA ĐỒ THỊ 1. Định nghĩa và các tính chất cơ bản Định nghĩa Cây là một đồ thị vô hướng liên thông không chứa chu trình và có ít nhất hai đỉnh. Một đồ thị vô hướng không chứa chu trình và có ít nhất hai đỉnh gọi là một rừng. Trong một rừng mỗi thành phần liên thông là một cây. 67 CHƯƠNG IV CÂY VÀ CÂY KHUNG CỦA ĐỒ THỊ 1. Định nghĩa và các tính chất cơ bản Định lý Cho T là một đồ thị có n 2 đỉnh. Các điều sau là tương đương 1 T là một cây. 2 T liên thông và có n 1 cạnh. 3 T không chứa chu trình và có n 1 cạnh. 4 T liên thông và mỗi cạnh là cầu. 5 Giữa hai đỉnh phân biệt bất kỳ của T luôn có duy nhất một đường đi đơn. 6 T không chứa chu trình nhưng khi thêm một cạnh mới thì có được một chu trình duy nhất. 68 CHƯƠNG IV CÂY VÀ CÂY KHUNG CỦA ĐỒ THỊ 2. Cây khung và bài toán tìm cây khung nhỏ nhất Định nghĩa Trong đồ thị liên thông G nếu ta loại bỏ cạnh nằm trên chu trình nào đó thì ta sẽ được đồ thị vẫn là liên thông. Nếu cứ loại bỏ các cạnh ở các chu trình khác cho đến khi nào đồ thị không còn chu trình vẫn liên thông thì ta thu được một cây nối các đỉnh của G. Cây đó gọi là cây khung hay cây bao trùm của đồ thị G. 69 CHƯƠNG IV CÂY VÀ CÂY KHUNG CỦA ĐỒ THỊ 2. Cây khung và bài toán tìm cây khung nhỏ nhất Bài toán được phát biểu như sau This image cann ot cur rently b e displayed. Cho G V E là đồ thị vô hướng liên thông có trọng số mỗi cạnh e E có trọng số m e 0. Giả sử T VT ET là cây khung của đồ thị G VT V . Ta gọi độ dài m T của cây khung T là tổng trọng số của các cạnh của nó m T m e e ET 70 CHƯƠNG IV CÂY VÀ CÂY KHUNG CỦA ĐỒ THỊ 2. Cây khung và bài toán tìm cây khung nhỏ nhất Bài toán đặt ra là trong số tất cả các cây khung của đồ thị G hãy tìm cây khung có độ dài nhỏ nhất. Cây khung như vậy được gọi là cây khung nhỏ nhất của đồ thị. Bài toán được gọi là bài toán tìm cây khung nhỏ nhất . Hai mô hình thực tế tiêu biểu Bài toán xây dựng hệ thống đường sắt. Bài toán nối mạng máy tính. 71 CHƯƠNG IV CÂY VÀ CÂY KHUNG CỦA ĐỒ THỊ 3. Thuật toán Kruskal

• Toán học
• Bài giảng Lý thuyết đồ thị
• Lý thuyết đồ thị
• Cây của đồ thị
• Cây khung của đồ thị
• Thuật toán Kruskal
• Thuật toán Prim
• Giới thiệu Lý thuyết đồ thị
• Môn học Lý thuyết đồ thị
• Đại cương Lý thuyết đồ thị
• Hình thức thi Lý thuyết đồ thị
• Đại cương về đồ thị
• Các mô hình đồ thị
• Thuật ngữ cơ bản của đồ thị
• Đường đi của đồ thị
• Sự liên thông đồ thị
• tài liệu về lý thuyết đồ thị
• học lý thuyết đồ thị tốt
• phương pháp học lý thuyết đồ thị
• hàm trên đồ thị
• Đơn đồ thị đặc biệt
• Đồ thị bánh xe
• Đồ thị con
• Mô hình đồ thị
• Lịch sử của lý thuyết đồ thị
• Ưng dụng của đồ thị
• Tổng quan lý thuyết đồ thị
• Bài toán 7 cái cầu
• Biểu diễn đồ thị trên máy tính
• Sự đẳng cấu của đồ thị
• Phương pháp biểu diễn đồ thị
• Biểu diễn đồ thị bằng ma trận kề
• Đồ thị Euler
• Đồ thị Hamilton
• Chu trình Hamilton
• Kiểm tra đồ thị Hamilton
• Đồ thị phẳng
• Bài toán tô màu đồ thị
• Công thức Euler
• Định lý Kuratowski
• Đồ thị không phẳng
• Tô màu đồ thị
• Bài toán lý thuyết đồ thi
• Bài toán lý thuyết đồ thị
• Bất đẳng thức EV
• Biểu diễn đồ thị
• Bậc của đỉnh
• Định nghĩa đồ thị
• Bài tập đồ thị
• Thuật toán tìm kiếm trên đồ thị
• Đồ thị Haminton
• Đồ thị đẳng cấu
• Đồ thị tổng vành; Đồ thị đơn giản
• Đồ thị liên thông
• Dạng đồ thị đặc biệt
• Chu trình của đồ thị
• Chiều sâu trên đồ thị
• Chiều rộng trên đồ thị
• Tìm kiếm chiều rộng trên đồ thị
• Tìm kiếm trên đồ thị
• Đồ thị hữu hạn
• Đẳng cấu đồ thị
• Các dạng đồ thị
• Toán ứng dụng