TAILIEUCHUNG - Giáo trình lý thuyết đồ thị - Bài 18

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. . Cây Khái niệm cây được Cayley đưa ra đầu tiên vào năm 1857. Định nghĩa : 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ụ : Đồ thị dưới đây là một cây. | 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. . Cây Khái niệm cây được Cayley đưa ra đầu tiên vào năm 1857. Định nghĩa 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ụ Đồ thị dưới đây là một cây. Hình . 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ý . 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

• Toán học
• Chu trình Hamilton
• thuật toán
• đồ thị
• ứng dụng cây
• hàm trên đồ thị
• Lý thuyết đồ thị
• Đường đi Hamilton
• Đồ thị Hamilton
• Định nghĩa về chu trình Hamilton
• Định nghĩa về đường đi Hamilton
• Đường Hamilton
• bài toán mã đi tuần
• chu trình vô hướng hamilton
• Luận án Tiến sĩ Toán học
• Luận án Tiến sĩ
• Cơ sở toán học cho tin học
• Thuật toán đa thức xác định chu trình Hamilton
• Bài giảng Lý thuyết đồ thị
• Đồ thị Euler
• Kiểm tra đồ thị Hamilton
• Bài toán người du lịch
• Bài toán tối ưu tổ hợp
• Đường Hamilton
• Thuật toán nhánh cận giải TSP
• Bài toán người du lịch và thuật toán nhánh cận
• Bài toán tối ưu liên quan đến đường Hamilton
• Đồ thị tách cực
• Đồ thị tách cực phi Hamilton tối đại
• Bậc cực tiểu
• Chu trình euler
• thuật toán tìm chu trình
• đồ thị liên thông
• Bài toán lý thuyết đồ thị
• Bài toán luông
• toán rời rạc
• bài tập học phần
• Đường đi đồ thị
• Đồ thị phẳng
• Bài toán tô màu đồ thị
• Tài liệu Thực hành
• Đồ thị Chu trình
• Lý thuyết đồ thị chu trình
• Đường đi Euler
• Đồ thị ơ2= N
• Đồ thị đơn
• Bài toán HC
• Thuật toán đa thức
• Xây dựng thuật toán đa thức
• Đồ thị 2 phần
• Đồ thị đầy đủ
• Đồ thị rỗng
• tài liệu toán học
• phép toán hedetniemi
• bài giảng toán học
• các bài toán về đường đi
• Bài giảng Toán rời rạc
• Thuật toán Dijkstra
• giáo trình đồ thị
• tài liệu về đồ thị
• ứng dụng của đồ thị
• Đường đi trên đồ thị
• Bài toán đường đi tốt nhất
• Bài giảng Cấu trúc rời rạc
• Cấu trúc rời rạc
• Chu trình và đường đi Euler
• Chu trình và đường đi Hamilton