tailieunhanh - Bài giảng Lý thuyết đồ thị: Chương 11 - PGS.TS. Hoàng Chí Thành

Bài giảng Lý thuyết đồ thị: Chương 11 Cây và một số ứng dụng, cung cấp cho người đọc những kiến thức như: Khái niệm cây; Cây bao trùm; Cây bao trùm nhỏ nhất; Cây bao trùm lớn nhất; Cây phân cấp; Cây nhị phân; Cây biểu thức; Cây mã tối ưu. Mời các bạn cùng tham khảo! | CHƯƠNG 11 CÂY VÀ MỘT SỐ ỨNG DỤNG 1 NỘI DUNG Khái niệm cây Cây bao trùm Cây bao trùm nhỏ nhất Cây bao trùm lớn nhất Cây phân cấp Cây nhị phân Cây biểu thức Cây mã tối ưu 2 . KHÁI NIỆM CÂY Khái niệm cây do Cayley đưa ra vào năm 1857. Định nghĩa Giả sử T V E là một đồ thị vô hướng. T là một cây nếu nó thỏa mãn hai tính chất sau - liên thông - không có chu trình. 3 VÍ DỤ Đồ thị dưới đây là một cây. b a c d e f g Hình . Cây 7 đỉnh 4 . KHÁI NIỆM CÂY tiếp Định lý Cho T là đồ thị vô hướng có số đỉnh không ít hơn 2. Khi đó các khẳng định sau là tương đương 1. T là một cây. 2. T không có chu trình và có n - 1 cạnh. 3. T liên thông và có n - 1 cạnh. 4. T không có chu trình nhưng nếu thêm một cạnh bất kỳ nối hai đỉnh không kề nhau thì có chu trình. 5. T liên thông nhưng nếu bớt đi một cạnh bất kỳ thì sẽ mất tính liên thông. 6. Chỉ có duy nhất một đường đi nối hai đỉnh bất kỳ. 5 . KHÁI NIỆM CÂY tiếp Chứng minh Chú ý rằng đồ thị T không có chu trình khi và chỉ khi chu số của nó bằng 0 nghĩa là m n - p. 1 2 Vì p 1 và m n - p suy ra m n - 1. 2 3 m n - p m n - 1 cho nên p 1. 3 4 p 1 m n - 1 suy ra m n - p. Vậy thì c T 0 đồ thị T không có chu trình. Thêm một cạnh vào thì m tăng thêm 1 còn n p không đổi. Khi đó chu số c T m - n p 1. Đồ thị có một chu trình. 6 . KHÁI NIỆM CÂY tiếp Chứng minh 4 5 c T 0 nên m n - p. Phản chứng đồ thị T không liên thông có ít nhất hai đỉnh a b không liên thông. Thêm cạnh a b vào đồ thị vẫn không có chu trình. Mâu thuẫn với điều 4 . Vậy đồ thị phải liên thông nghiã là p 1. Suy ra m n - 1. Khi bớt đi một cạnh bất kỳ đồ thị vẫn không có chu trình. Do đó m - 1 n - p . Suy ra p 2 và đồ thị mất tính liên thông. 7 . KHÁI NIỆM CÂY tiếp Chứng minh 5 6 Đồ thị T liên thông nên có đường đi đơn nối mỗi cặp đỉnh. Giả sử cặp đỉnh a b được nối bằng hai đường đi đơn khác nhau. Khi đó có cạnh e thuộc đường đi này nhưng không thuộc đường đi kia. Ta bỏ cạnh e này đi đồ thị vẫn liên thông. Trái với điều 5 . 8 . KHÁI NIỆM CÂY tiếp Chứng