tailieunhanh - 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,. . | TRƯỜNG CAO ĐẲNG CÔNG NGHỆ THÔNG TIN KHOA CÔNG NGHỆ THÔNG TIN MÔN TOÁN RỜI RẠC VÀ LÝ THUYẾT ĐỒ THỊ CHƯƠNG 6 CÂY VÀ CÂY KHUNG ĐỒ THỊ GV: Võ Tấn Dũng votandung@ Cây và các tính chất cơ bản Định nghĩa Cây Cho 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ông của nó là một cây. Rừng cây Ví dụ: a b c d e f G1 a b c d f e G2 a b c d f e a b c d f e G3 G1, G2 là cây; G3, G4 không phải là cây G4 Đị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ào một cạnh ta thu được đúng một chu trình. Cây khung đồ thị Giới thiệu Cá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ị G' vẫ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ình khác cho đến khi đồ thị T không còn chu trình nhưng vẫn liê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 đồ .

• Toán học
• Bài giảng Toán rời rạc
• Toán rời rạc
• Lý thuyết đồ thị
• Cây khung đồ thị
• Khung đồ thị
• Thuật toán Prim
• Thuật toán Kruskal
• 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