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,...).
Nội dung trích xuất từ tài liệu:
Bài giảng Lý thuyết đồ thị: Chương 5 - Cây và cây khung của đồ thị Chương 5Cây và Cây khung của đồ thị Phần 5.1.Các khái niệm cơ bản về câyCâ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.Lý thuyết đồ thị 11/26/15 3Câ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ìnhLý thuyết đồ thị 11/26/15 4Câ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âyLý thuyết đồ thị 11/26/15 5Tí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.Lý thuyết đồ thị 11/26/15 6 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 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) Lý thuyết đồ thị 11/26/15 7 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 chứng minh T liên thông.  Giả sử T có k thành phần liên thông với số đỉnh lần lượt là n ,…, n . 1 k  Khi đó mỗi thành phần liên thông của T sẽ là một cây và sẽ có số cạnh lần lượt là n1-1, n2-1,…, nk-1.  Suy ra, số cạnh của T sẽ là n1-1 + n2-1 +…+ nk-1 = n – k.  Theo giả thiết, số cạnh của cây là n-1. Từ đó suy ra k = 1 hay T chỉ có 1 thành phần liên thông. Suy ra T liên thông (đpcm). Lý thuyết đồ thị 11/26/15 8 Tính chất của cây (tt) Chứng minh định lý (tt):  (3) (4): 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)  Hiển nhiên T liên thông (theo giả thiết)  Ta chỉ cần chứng minh mỗi cạnh của T đều là cạnh cắt (cầu).  Xét (u,v) là cạnh bất kỳ của T. Nếu bỏ (u,v) ra khỏi T, ta sẽ được đồ thị T’ có n đỉnh và n-2 cạnh.  Ta đã chứng minh được đồ thị có n đỉnh và n-2 cạnh thì không thể liên thông.  Vậy nếu bỏ cạnh (u,v) ra thì sẽ làm mất tính liên thông của đồ thị. Suy ra (u,v) là cạnh cắt (cầu). (đpcm). Lý thuyết đồ thị 11/26/15 9 Tính chất của cây (tt) Chứng minh định lý (tt):  (4) (5): T liên thông và mỗi cạnh của T đều là cạnh cắt (cầu) Giữa hai đỉnh bất kỳ của T luôn tồn tại đúng 1 đường đi đơn  Xét u, v là hai đỉnh bất kỳ trong T.  Do T liên thông nên luôn tồn tại đường đi giữa u và v. Ta sẽ chứng minh đường đi này là duy nhất.  Giả sử có hai đường đi đơn khác nhau giữa u và v. Khi đó hai đường đi này sẽ tạo thành một chu trình.  Suy ra, các cạnh trên chu trình này sẽ không thể là cạnh cắt được (???) – Mâu thuẫn.  Vậy giữa u và v chỉ có thể tồn tại đúng 1 đường đi đơn. (đpcm) Lý thuyết đồ thị 11/26/15 10 Tính chất của cây (tt) Chứng minh định lý (tt):  (5) (6): Giữa hai đỉnh bất kỳ của T luôn tồn tại đúng 1 đường đi đơn T không chứa chu trình, nhưng nếu thêm vào 1 cạnh bất kỳ thì sẽ phát sinh đúng 1 chu trình T không thể có chu trình, vì nếu có chu trình thì giữa hai đỉnh trên chu trình này sẽ có 2 đường đi đơn khác nhau – mâu thuẫn với GT.  Giả sử ta thêm vào T cạnh (u,v) bất kỳ (trước đó không có cạnh này trong T).  Khi đó cạnh này sẽ tạo với đường đi duy nhất giữa u và v trong T tạo thành 1 chu trình duy nhất. (Vì nếu tạo thành 2 chu trình thì chứng tỏ trước đó có 2 đường đi khác nhau giữa u và v – mâu thuẫn với giả thiết) Lý thuyết đồ thị 11/26/15 11 Tính chất của cây (tt ...