TAILIEUCHUNG - Bài giảng Toán rời rạc - Phần 8: Cây (TS. Nguyễn Viết Đông)

Bài giảng Toán rời rạc - Phần 8: Cây (TS. Nguyễn Viết Đông) cung cấp cho học viên những kiến thức về định nghĩa và tính chất cây, cây khung ngắn nhất, cây có gốc, phép duyệt cây, thuật toán tìm cây khung, thuật toán ưu tiên chiều sâu, thuật toán Kruscal, thuật toán Prim, phép duyệt tiền thứ tự, . Mời các bạn cùng tham khảo chi tiết nội dung bài giảng! | Cây Biên so ạn ễn Vi ết Đông Cây 1. ĐN và tính chất 2. Cây khung ngắn nhất 3. Cây có gốc 4. Phép duyệt cây 2 Định nghĩa và tính chất Định nghĩa Cây. a Cho G là đồ thị vô hướng. G được gọi là một cây nếu G liên thông và không có chu trình sơ cấp. b Rừng là đồ thị mà mỗi thành phần liên thông của nó là một cây. 3 Định nghĩa và tính chất 1 2 4 3 10 5 9 8 6 7 11 12 13 15 16 17 14 4 Định nghĩa và tính chất Điều kiện cần và đủ. Cho T là đồ thị vô hướng có n đỉnh. Các phát biểu sau đây là tương đương i. T là cây. ii. T liên thông và có n 1 cạnh. iii. T không có chu trình sơ cấp và có n 1 cạnh . iv. T liên thông và mỗi cạnh là một cầu. v. Giữa hai đỉnh bất kỳ có đúng một đường đi sơ cấp nối chúng với nhau. 5 Định nghĩa và tính chất 1 2 4 3 10 5 9 8 6 7 11 12 13 15 16 17 14 6 Định nghĩa và tính chất Định nghĩa cây khung. Cho G V E là đồ thị vô hướng. T là đồ thị con khung của G. Nếu T là một cây thì T được gọi là cây khung hay cây tối đại hay cây bao trùm của đồ thị G. Thuật toán tìm cây khung. 7 Breadth first Search Algorithm .Thuật toán ưu tiên chiều rộng Cho G là đồ thị liên thông với tập đỉnh v1 v2 vn Bước 0 thêm v1 như là gốc của cây rỗng. Bước 1 thêm vào các đỉnh kề v1 làm con của nó và các cạnh nối v1 với chúng. Những đỉnh này là đỉnh mức 1 trong cây. Bước 2 đối với mọi đỉnh v mức1 thêm vào các cạnh kề với v vào cây sao cho không tạo nên chu trình đơn. Thu được các đỉnh mức 2. . Tiếp tục quá trình này cho tới khi tất cả các đỉnh của đồ thị được ghép vào cây. CâyT thu được là cây khung của đồ thị. Ví dụ. Xét đồ thị liên thông G. b c l a e e f d b d f g i h i j Chọn e làm gốc m k Các đỉnh kề với e là con của nó. Các đỉnh mức 1 là b d f i b c l a e e f f d b d g i c h h a k i j g j m k Thêm a và c làm con của b h là con duy nhất của d g và j là con của f k là con duy nhất của i Các đỉnh mức 2 là a c h g j k b c l a e e f f d b d g i c h h a k i j g j m k l m n Cuối cùng thêm l và m là con của g và k tương ứng Các đỉnh mức 3 là l m Depth first Search Algorithm .

• Toán học
• Bài giảng Toán rời rạc
• Toán rời rạc
• Cây khung ngắn nhất
• Cây có gốc
• Phép duyệt cây
• Thuật toán tìm cây khung
• 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
• Câu hỏi Toán rời rạc
• Bài tập Toán rời rạc
• Hệ thức truy hồi
• Quan hệ chia để trị Toán rời rạc
• Nguyên lý toán rời rạc
• Cấu hình tổ hợp
• Cấu hình toán rời rạc
• Bài giảng môn học Toán học rời rạc
• Toán học rời rạc
• Môn Toán học rời rạc
• Tập hợp và logic mệnh đề
• lý thuyết toán rời rạc
• đề cương Toán rời rạc