Đang chuẩn bị liên kết để tải về tài liệu:
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 TS.Nguy ễ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 .