tailieunhanh - Bài giảng Lý thuyết đồ thị: Chương 5 - Cây và cây khung của đồ thị

Sau đây là bài giảng Lý thuyết đồ thị: Chương 5 - Cây và cây khung của đồ thị. Mời các bạn tham khảo bài giảng để bổ sung thêm kiến thức về các khái niệm và tính chất cơ bản về cây; cây khung (định nghĩa, đồ thị có trọng số, thuật toán Prim, thuật toán Kruskal,.). | Chương 5 Cây và Cây khung của đồ thị Phần . Các khái niệm cơ bản về cây 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. 5/14/2020 4:53:08 AM Lý thuyết đồ thị Cây (tt) VD: Trong các đồ thị sau, đồ thị nào là cây? G1, G2 là cây. G3, G4 không là cây do có chứa chu trình 5/14/2020 4:53:08 AM Lý thuyết đồ thị 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 5/14/2020 4:53:08 AM Lý thuyết đồ thị 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: T là cây. 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. T liên thông và mỗi cạnh của T đều là cạnh cắt (cầu). Hai đỉnh bất kỳ của T được nối với nhau bằng đúng 1 đường đi đơn. T không chứa chu trình nhưng nếu thêm | Chương 5 Cây và Cây khung của đồ thị Phần . Các khái niệm cơ bản về cây 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. 5/14/2020 4:54:39 AM Lý thuyết đồ thị Cây (tt) VD: Trong các đồ thị sau, đồ thị nào là cây? G1, G2 là cây. G3, G4 không là cây do có chứa chu trình 5/14/2020 4:54:39 AM Lý thuyết đồ thị 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 5/14/2020 4:54:39 AM Lý thuyết đồ thị 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: T là cây. 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. T liên thông và mỗi cạnh của T đều là cạnh cắt (cầu). Hai đỉnh bất kỳ của T được nối với nhau bằng đúng 1 đường đi đơn. 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/14/2020 4:54:39 AM Lý thuyết đồ thị 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 Tn là cây có n đỉnh. Ta sẽ chứng minh quy nạp theo 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 Tk+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 Tk+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) 5/14/2020 4:54:39 AM Lý thuyết đồ thị 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) .