Bài giảng Toán rời rạc và lý thuyết đồ thị: Bài 6 - Võ Tấn Dũng

Phần tiếp theo bài giảng "Toán rời rạc và lý thuyết đồ thị - Bài 6: Cây và cây khung đồ thị" cung cấp cho người học các kiến thức: Cây và các tính chất cơ bản, cây khung đồ thị, định nghĩa cây khung đồ thị, thuật toán Prim, thuật toán Kruskal,... 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 rời rạc và lý thuyết đồ thị: Bài 6 - Võ Tấn DũngTRƯỜNG CAO ĐẲNG CÔNG NGHỆ THÔNG TIN TP.HCMKHOA CÔNG NGHỆ THÔNG TINMÔN TOÁN RỜI RẠC VÀ LÝ THUYẾT ĐỒ THỊCHƯƠNG 6CÂY VÀ CÂY KHUNG ĐỒ THỊGV: Võ Tấn Dũngvotandung@yahoo.comCây và các tính chất cơ bảnĐịnh nghĩa CâyCho G=(V,E) là đồ thị vô hướng. G được gọi là một Cây(tree) nếu và nếu G liên thông và không có chu trìnhđơn.Định nghĩa Rừng- Rừng (forest) là đồ thị mà mỗi thành phần liên thôngcủa nó là một cây.RừngcâyVí dụ:abcdefG1abcdfeG2abcdfeabcdfeG3G1, G2 là cây; G3, G4 không phải là câyG4Định lýĐịnh lý: Giả sử G=(V,E) là đồ thị vô hướng n đỉnh.Khi đó các mệnh đề sau đây là tương đương:•••••(1) T là 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) Hai đỉnh bất kỳ của T được nối với nhau bởiđúng một đường đi đơn;• (6) T không chứa chu trình nhưng hễ cứ thêm vàomột cạnh ta thu được đúng một chu trình.Cây khung đồ thịGiới thiệuCách tạo cây khung của đồ thịTrong đồ thị liên thông G, chúng ta thực hiện loại bỏmột cạnh nằm trên một chu trình nào đó sẽ tạo ra đồ thị Gvẫn có tính liên thông.Thực hiện tiếp việc loại bỏ các cạnh ở các chu trìnhkhác cho đến khi đồ thị T không còn chu trình nhưng vẫnliên thông thì chúng ta thu được một cây nối tất cả cácđỉnh của G - gọi là cây khung của đồ thị.