tailieunhanh - Bài giảng Lý thuyết đồ thị - Bài 4: Cây (Tree)

Bài giảng "Lý thuyết đồ thị - Bài 4: Cây (Tree)" cung cấp cho người học các kiến thức: Các khái niệm cơ bản về cây, tính chất của cây, cây có gốc, cây nhị phân, một số tính chất của cây nhị phân,. nội dung chi tiết. | Bài giảng Lý thuyết đồ thị - Bài 4: Cây (Tree) Bài 4 Cây (Tree) Các khái niệm cơ bản về Cây Định nghĩa: Cây là một đơn đồ thị vô hướng, liên thông và không chứa chu trình. Ví dụ: Trong các đồ thị sau, đồ thị nào là cây? Cả 3 đồ thị trên đều là cây. 2 Cây (tt) VD: Trong các đồ thị sau, đồ thị nào là cây? G1, G2 là cây. G3 không là cây do có chứa chu trình, G4 không liên thông 3 Cây (tt) Định nghĩa: Nếu G là một đồ thị vô hướng và không chứa chu trình thì G được gọi là một rừng. Khi đó mỗi thành phần liên thông của G sẽ là một cây. VD: Đồ thị trên là rừng có 3 cây 4 Tính chất của cây Định lý: Cho T là một đồ thị vô hướng. Khi đó, các điều 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 T đều là cạnh cắt (cầu). 5. Hai đỉnh bất kỳ của T được nối với nhau bằng đúng 1 đường đi đơn. 6. T không chứa chu trình nhưng nếu thêm 1 cạnh bất kỳ vào T thì ta sẽ được thêm đúng 1 chu trình. 5 Tính chất của cây (tt) Chứng minh định lý: (1) (2): T là cây T không chứa chu trình và có n-1 cạnh Hiển nhiên T không chứa chu trình (do T là cây) Ta chỉ cần chứng minh T có n-1 cạnh. Xét T là cây có n đỉnh. Ta sẽ chứng minh quy nạp theo n n – n = 2, Cây có 2 đỉnh thì có 1 cạnh. Đúng. – Giả sử mọi cây có k đỉnh thì sẽ có k-1 cạnh – Xét Tk+1 là cây có k + 1 đỉnh. Dễ thấy rằng trong cây Tk+1 luôn tồn tại ít nhất 1 đỉnh treo. – Loại đỉnh treo này (cùng với cạnh nối) ra khỏi T k+1 ta được đồ thị T’ có k đỉnh. Dễ thấy T’ vẫn liên thông và không có chu trình (do T k+1 không có chu trình) – Suy ra T’ là cây. Theo giả thiết quy nạp, T’ có k đỉnh thì sẽ có k-1 cạnh. Vậy cây Tk+1 có k cạnh. (đpcm) 6 Tính chất của cây (tt) Chứng minh định lý (tt): (2) (3): T không chứa chu trình và có n-1 cạnh T liên thông và có n-1 cạnh Hiển nhiên T có n-1 cạnh (theo giả thiết) Ta chỉ cần