Đang chuẩn bị liên kết để tải về tài liệu:
BÀI 18_Chương 11: Cây và một số ứng dụng

Trong chương này ta xét một dạng đặc biệt nhưng có nhiều ứng dụng của đồ thị vô hướng. Đó là khái niệm cây. 11.1. Cây Khái niệm cây được Cayley đưa ra đầu tiên vào năm 1857. Định nghĩa 11.1: Giả sử T = (V, E) là đồ thị vô hướng. Ta nói rằng đồ thị T là một cây nếu nó liên thông và không có chu trình. Ví dụ 11.2: Đồ thị dưới đây là một cây. Kết quả dưới đây sẽ cho chúng ta một số tính chất lý thú và có thể dùng làm. | BÀI 18 Chương 11 Cây và một số ứng dụng Trong chương này ta xét một dạng đặc biệt nhưng có nhiều ứng dụng của đồ thị vô hướng. Đó là khái niệm cây. 11.1. Cây Khái niệm cây được Cayley đưa ra đầu tiên vào năm 1857. Định nghĩa 11.1 Giả sử T V E là đồ thị vô hướng. Ta nói rằng đồ thị T là một cây nếu nó liên thông và không có chu trình. Ví dụ 11.2 Đồ thị dưới đây là một cây. Hình 11.1. Cây 7 đỉnh Kết quả dưới đây sẽ cho chúng ta một số tính chất lý thú và có thể dùng làm định nghĩa cho cây. Định lý 11.1. Với đồ thị vô hướng T có số đỉnh không ít hơn 2 các tính chất sau đây là tương đương T là một cây. T không có chu trình và có n-1 cạnh. T liên thông và có n-1 cạnh. T không có chu trình nhưng nếu thêm một cạnh nối hai đỉnh bất kỳ không kề nhau thì xuất hiện một chu trình. 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. Mỗi cặp đỉnh được nối với nhau bằng đúng một đường đi đơn. 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ì chu số của đồ thị 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 m - n p 1. Đồ thị có một chu trình. 4 5 c 0 nên m n - p. Giả sử ngược lại đồ thị T không liên thông. Thế thì có ít nhất hai đỉnh a b không liên thông. Khi thêm cạnh a b vào đồ thị vẫn không làm xuất hiện 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 . Thế thì p 2 và đồ thị mất tính liên thông. 5 6 Vì đồ thị T liên thông nên mỗi cặp đỉnh đều có đường đi đơn nối chúng. 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 . 6 1 Suy ra đồ thị T liên thông. Giả sử T có chu trình. Vậy thì giữa