Bài giảng Toán học tổ hợp - Chương 2: Cây

Bài giảng Toán học tổ hợp - Chương 2: Cây cung cấp cho người học những kiến thức như: Định nghĩa và tính chất; Cây khung ngắn nhất; Cây có gốc; Phép duyệt cây. Mời các bạn cùng tham khảo!
Nội dung trích xuất từ tài liệu:
Bài giảng Toán học tổ hợp - Chương 2: CâyChương 2. CÂY LVL @2020Nội dung ▪ Định nghĩa và tính chất ▪ Cây khung ngắn nhất ▪ Cây có gốc ▪ Phép duyệt cây 21. Định nghĩa và tính chấtĐịnh nghĩa. Cây (tree) là đồ thị vô hướng, liên thôngvà không có chu trình B E B E F F A A C D C D G1 G2 G1 là cây, G2 không phải cây 3Cây 4RừngĐịnh nghĩa. Rừng (forest) là đồ thị vô hướng khôngcó chu trình B G I L J A C F K D E HNhận xét. Rừng là đồ thị mà mỗi thành phần liên thôngcủa nó là một cây. 5Rừng 6Tính chất của câyĐịnh lý: Cho đồ thị vô hướng T có n đỉnh. Khi đó cácphát biểu sau là tương đương: 1) T là 1 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) Giữa hai đỉnh bất kỳ của T có đúng một đường đi nối chúng với nhau 6) T không chứa chu trình nhưng khi thêm vào một cạnh nối hai đỉnh của T ta thu được đúng một chu trình 7Hệ quả.a) Một cây có ít nhất 2 đỉnh treob) Nếu G là một rừng có n đỉnh và có p cây thì số cạnh của G là m=n-p 8Cây khung của đồ thịĐịnh nghĩa: Một cây T được gọi là cây khung (haycây tối đại, cây bao trùm) của đồ thị G=(V, E) nếu T làđồ thị con của G và chứa tất cả các đỉnh của G.Ví dụ. Cho đồ thị C D A F B EHãy tìm cây khung của G? 9Cây khung của đồ thị C DĐáp án. Một số cây khung của G A F B E C D C D A F A F B E B E Nhận xét. Với 1 đồ thị cho trước, có thể có vài cây khung của đồ thị đó 10Định lý. Mọi đồ thị liên thông đều có cây khungĐịnh lý (Cayley) Số cây khung của đồ thị Kn là nn-2 a Số cây khung 44-2=16 d f b Ví dụ: abc, bcd, cda, dab, abf, acf, bdf, ... c e A B C Số cây khung 55-2=125 D E 11Tìm một cây khung của đồ thịBài toán: Cho G là đồ thị vô hướng liên thông, hãytìm 1 cây khung của đồ thị G.Để giải bài này ta dùng 2 thuật toán sau • Thuật toán tìm kiếm theo chiều rộng (BFS) Breadth-first search • Thuật toán tìm kiếm theo chiều sâu (DFS) Depth-first search 12Tìm kiếm theo chiều rộng (BFS)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 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ức 1, 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. Ta 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ây T có được là cây khung của đồthị. 13Ví dụ. Tìm một cây khung của đồ thị G. b c l e a e f d d b f g i h i j Chọn e làm gốc m k Chọn các đỉnh kề với e. Các đỉnh mức 1 là: b, d, f, i 14 b c l ea e f ...