TAILIEUCHUNG - Bài giảng Lý thuyết đồ thị - Bài 4: Cây (Tree)

Bài giảng "Lý thuyết đồ thị - Bài 4: Cây (Tree)" cung cấp cho người học các kiến thức: Các khái niệm cơ bản về cây, tính chất của cây, cây có gốc, cây nhị phân, một số tính chất của cây nhị phân,. nội dung chi tiết. | Bài giảng Lý thuyết đồ thị - Bài 4: Cây (Tree) Bài 4 Cây (Tree) Các khái niệm cơ bản về 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. 2 Cây (tt) VD: Trong các đồ thị sau, đồ thị nào là cây? G1, G2 là cây. G3 không là cây do có chứa chu trình, G4 không liên thông 3 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 4 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: 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. 5 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 T k+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 T k+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) 6 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

• Toán học
• Bài giảng Lý thuyết đồ thị
• Lý thuyết đồ thị
• Cây nhị phân
• Duyệt cây nhị phân
• Biểu diễn cây nhị phân
• Cây có gốc
• Giới thiệu Lý thuyết đồ thị
• Môn học Lý thuyết đồ thị
• Đại cương Lý thuyết đồ thị
• Hình thức thi Lý thuyết đồ thị
• Đại cương về đồ thị
• Các mô hình đồ thị
• Thuật ngữ cơ bản của đồ thị
• Đường đi của đồ thị
• Sự liên thông đồ thị
• tài liệu về lý thuyết đồ thị
• học lý thuyết đồ thị tốt
• phương pháp học lý thuyết đồ thị
• hàm trên đồ thị
• Đơn đồ thị đặc biệt
• Đồ thị bánh xe
• Đồ thị con
• Mô hình đồ thị
• Lịch sử của lý thuyết đồ thị
• Ưng dụng của đồ thị
• Tổng quan lý thuyết đồ thị
• Bài toán 7 cái cầu
• Biểu diễn đồ thị trên máy tính
• Sự đẳng cấu của đồ thị
• Phương pháp biểu diễn đồ thị
• Biểu diễn đồ thị bằng ma trận kề
• Đồ thị Euler
• Đồ thị Hamilton
• Chu trình Hamilton
• Kiểm tra đồ thị Hamilton
• Đồ thị phẳng
• Bài toán tô màu đồ thị
• Công thức Euler
• Định lý Kuratowski
• Đồ thị không phẳng
• Tô màu đồ thị
• Bài toán lý thuyết đồ thi
• Bài toán lý thuyết đồ thị
• Bất đẳng thức EV
• Biểu diễn đồ thị
• Bậc của đỉnh
• Định nghĩa đồ thị
• Bài tập đồ thị
• Thuật toán tìm kiếm trên đồ thị
• Đồ thị Haminton
• Cây khung của đồ thị
• Đồ thị đẳng cấu
• Đồ thị tổng vành; Đồ thị đơn giản
• Đồ thị liên thông
• Dạng đồ thị đặc biệt
• Chu trình của đồ thị
• Chiều sâu trên đồ thị
• Chiều rộng trên đồ thị
• Tìm kiếm chiều rộng trên đồ thị
• Tìm kiếm trên đồ thị
• Đồ thị hữu hạn
• Đẳng cấu đồ thị
• Các dạng đồ thị
• Toán ứng dụng