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

TRƯỜNG CAO ĐẲNG CÔNG NGHỆ THÔNG TIN TP.HCM<br /> KHOA CÔNG NGHỆ THÔNG TIN<br /> <br /> MÔN TOÁN RỜI RẠC VÀ LÝ THUYẾT ĐỒ THỊ<br /> <br /> CHƯƠNG 6<br /> <br /> CÂY VÀ CÂY KHUNG ĐỒ THỊ<br /> GV: Võ Tấn Dũng<br /> votandung@yahoo.com<br /> <br /> Cây và các tính chất cơ bản<br /> Định nghĩa Cây<br /> Cho G=(V,E) là đồ thị vô hướng. G được gọi là một Cây<br /> (tree) nếu và nếu G liên thông và không có chu trình<br /> đơn.<br /> Định nghĩa Rừng<br /> - Rừng (forest) là đồ thị mà mỗi thành phần liên thông<br /> của nó là một cây.<br /> <br /> Rừng<br /> <br /> cây<br /> <br /> Ví dụ:<br /> a<br /> <br /> b<br /> <br /> c<br /> <br /> d<br /> <br /> e<br /> <br /> f<br /> G1<br /> <br /> a<br /> <br /> b<br /> <br /> c<br /> <br /> d<br /> <br /> f<br /> <br /> e<br /> G2<br /> <br /> a<br /> <br /> b<br /> <br /> c<br /> <br /> d<br /> <br /> f<br /> <br /> e<br /> <br /> a<br /> <br /> b<br /> <br /> c<br /> <br /> d<br /> <br /> f<br /> <br /> e<br /> <br /> G3<br /> <br /> G1, G2 là cây; G3, G4 không phải là cây<br /> <br /> G4<br /> <br /> Định lý<br /> Định lý: Giả sử G=(V,E) là đồ thị vô hướng n đỉnh.<br /> Khi đó các mệnh đề sau đây là tương đương:<br /> •<br /> •<br /> •<br /> •<br /> •<br /> <br /> (1) T là cây;<br /> (2) T không chứa chu trình và có n-1 cạnh;<br /> (3) T liên thông và có n-1 cạnh;<br /> (4) T liên thông và mỗi cạnh của nó đều là cầu;<br /> (5) Hai đỉnh bất kỳ của T được nối với nhau bởi<br /> đúng một đường đi đơn;<br /> • (6) T không chứa chu trình nhưng hễ cứ thêm vào<br /> một cạnh ta thu được đúng một chu trình.<br /> <br /> Cây khung đồ thị<br /> Giới thiệu<br /> Cách tạo cây khung của đồ thị<br /> Trong đồ thị liên thông G, chúng ta thực hiện loại bỏ<br /> một cạnh nằm trên một chu trình nào đó sẽ tạo ra đồ thị G'<br /> vẫn có tính liên thông.<br /> Thực hiện tiếp việc loại bỏ các cạnh ở các chu trình<br /> khác cho đến khi đồ thị T không còn chu trình nhưng vẫn<br /> liên thông thì chúng ta thu được một cây nối tất cả các<br /> đỉnh của G - gọi là cây khung của đồ thị.<br /> <br />