Định nghĩa Cho đồ thị G = , G được gọi là một cây nếu G liên thông và không có chu trình, ở đây n = X 1. Khi đó sáu tính chất sau là tương đương 1) G là đồ thị liên thông và không có chu trình 2) G không có chu trình và có n - 1 cạnh 3) G liên thông và có n - 1 cạnh 4) G không có chu trình và nếu thêm vào một cạnh nối 2 đỉnh không kề nhau thì G xuất hiện duy nhất một chu trình | Luận văn tốt nghiệp - Một số vấn đề về cây Luận văn tốt Chương 5 MỘT SỐ VẤN ĐỀ VỀ CÂY I. CÁC KHÁI NIỆM VÀ TÍNH CHẤT CƠ BẢN 1. Định nghĩa Cho đồ thị G = , G được gọi là một cây nếu G liên thông và không có chu trình, ở đây n = X > 1. Khi đó sáu tính chất sau là tương đương 1) G là đồ thị liên thông và không có chu trình 2) G không có chu trình và có n - 1 cạnh 3) G liên thông và có n - 1 cạnh 4) G không có chu trình và nếu thêm vào một cạnh nối 2 đỉnh không kề nhau thì G xuất hiện duy nhất một chu trình. 5) G liên thông và nếu bỏ đi một cạnh tuỳ ý thì đồ thị nhận được sẽ không liên thông. 6) Mỗi cặp đỉnh trong G được nối với nhau bằng một đường duy nhất. Chứng minh: Ta chứng minh theo trình tự sau: 1) 2) 3) 4) 5) 6) 1). Ta sử dụng đẳng thức v(G) = m - n + p là số chu trình độc lập của đồ thị G = , ở đây X = n, U = m và p là số thành phần liên thông của G. 1) 2): Vì G không có chu trình nên v(G) = m - n + p = 0. Do G liên thông nên p =1 khi đó m - n + 1 = 0 hay số cạnh m = n - 1. 2) 3): Giả sử G không có chu trình và n - 1 cạnh ta chứng minh 3) Thật vậy, giả sử ngược lại G không liên thông, khi đó p 2 . Từ 2) ta có v(G) = m - n + p = 0 và m = n -1, kết hợp ta có (n - 1) - n + p = 0 hay p = 1, trái với giả thiết p 2. Vậy G liên thông và số cạnh là n -1. 3) 4): Giả sử G là liên thông và có n - 1 cạnh, ta chứng minh 4). Thật vậy vì G liên thông nên p = 1, mặt khác m = n - 1 nên v(G) = m - n + 1 = 0 hay G không có chu trình . Nếu thêm vào G một cạnh thì ta được đồ thị G' với số cạnh là n, hay v(G') = n - n + 1 = 1 hay G' có một chu trình. 4) 5): Giả sử ngược lại G không liên thông, tức là tồn tại cặp đỉnh x, y trong G mà không có đường nào nối x với y. Khi đó nối x và y bởi 1 cạnh, đồ thị nhận được vẫn không có chu trình điều này mâu thuẫn với 4). Hay G là liên thông. 56 Luận văn tốt Nếu bỏ đi 1 cạnh trong G mà đồ thị vẫn liên thông thì nếu khôi phục lại cạnh này đồ thị sẽ có chu trình. Điều này mâu thuẫn với 4). Vậy .
