tailieunhanh - Bài giảng Cây

Đị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. Định nghĩa và tính chất 1 4 3 10 9 6 11 12 13 14 7 8 15 16 17 2 5 3 4 1 .Đị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ây Cây Biên soạn Viết Đông 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 1 Đ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. vi. T không có chu trình sơ cấp và nếu thêm vào một cạnh giữa hai đỉnh không kề nhau thì có một chu trình sơ cấp duy nhất. 5 Đị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ứcl 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ị. 2 k là con duy nhất của i Các đỉnh mức 2 là a c h g j k k m 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 Thuật toán ưu tiên chiều sâu Cho G là đồ thị liên thông với tập đỉnh v1 v2 . vn Chọn một đỉnh tùy ý của đồ thị làm gốc. Xây dựng đường đi từ đỉnh này băng cách lượt ghép các cạnh sao cho mỗi cạnh mới ghép sẽ nối đỉnh cuối cùng trên đường đi với một đỉnh còn chưa thuộc đường tục ghép thêm cạnh vào đường đi chừng nào không thê thêm được nữa.