tailieunhanh - Bài giảng môn Lý thuyết đồ thị - Chương 4: Bài toán cây khung nhỏ nhất

Bài giảng Lý thuyết đồ thị - Chương 4: Bài toán cây khung nhỏ nhất, cung cấp cho người đọc những kiến thức như: Cây và các tính chất cơ bản của cây; Cây khung của đồ thị; Xây dựng tập các chu trình cơ bản của đồ thị; Xây dựng cây theo chiều sâu và chiều rộng; Bài toán cây khung nhỏ nhất. Mời các bạn cùng tham khảo! | Chương 4 Bài toán cây khung nhỏ nhất The Minimum Spanning Tree Problem Nội dung . Cây và các tính chất cơ bản của cây . Cây khung của đồ thị . Xây dựng tập các chu trình cơ bản của đồ thị . Xây dựng cây theo chiều sâu và chiều rộng . Bài toán cây khung nhỏ nhất 2 Cây và rừng Tree and Forest Định nghĩa 1. Ta gọi cây là đồ thị vô hướng liên thông không có chu trình. Đồ thị không có chu trình được gọi là rừng. Như vậy rừng là đồ thị mà mỗi thành phần liên thông của nó là một cây. T1 T2 T3 Rừng F gồm 3 cây T1 T2 T3 3 VÍ DỤ G1 G2 là cây G3 G4 không là cây 4 Các tính chất cơ bản của cây Định lý 1. Giả sử T V E là đồ thị vô hướng n đỉnh. Khi đó các mệnh đề sau đây là tương đương MĐ1 T là cây T liên thông và không chứa chu trình . MĐ2 T không chứa chu trình và có n-1 cạnh. MĐ3 T liên thông và có n-1 cạnh. MĐ4 T liên thông và mỗi cạnh của nó đều là cầu. MĐ5 Hai đỉnh bất kỳcủa T được nối với nhau bởi đúng 1 đường đi đơn. MĐ6 T không chứa chu trình nhưng hễcứthêm vào nó một cạnh ta thu được đúng 1 chu trình. 5 Nội dung . Cây và các tính chất cơ bản của cây . Cây khung của đồ thị . Xây dựng tập các chu trình cơ bản của đồ thị . Xây dựng cây theo chiều sâu và chiều rộng . Bài toán cây khung nhỏ nhất 6 Cây khung của đồ thị Định nghĩa 2. Giả sử G V E là đồ thị vô hướng liên thông. Cây T V F với F E được gọi là cây khung của đồ thị G. b c b c b c a d a d a d e e e G T1 T2 Đồ thị G và 2 cây khung T1 và T2 của nó 7 Số lượng cây khung của đồ thị Định lý sau đây cho biết số lượng cây khung của đồ thị đầy đủ Kn Định lý 2 Cayley . Số cây khung của đồ thị Kn là nn-2 . Arthur Cayley 1821 1895 b a b c b c a a c c a b K3 Ba cây khung của K3 8 methane H ethane H H C H H C H H H H C H propane H H C H H H C H H C H H C H H C H butane H C H H C H H H saturated hydrocarbons CnH2n 2 9 Ví dụ Các cây khung của đồ thị abc bcd cda dab afc dfb aec deb aed afb bec cfd efc efd efa efb. Số cây khung là 42 16 10 Nội dung . Cây và các tính chất cơ bản của cây . Cây .