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

Chia sẻ: N N | Ngày: | Loại File: PDF | Số trang:17

0
8
lượt xem
2
download

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

Mô tả tài liệu
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

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.

Chủ đề:
Lưu

Nội dung Text: 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 />

CÓ THỂ BẠN MUỐN DOWNLOAD

Đồng bộ tài khoản