TAILIEUCHUNG - Bài giảng Lý thuyết đồ thị: Chương 6 - Tôn Quang Toại

Bài giảng Lý thuyết đồ thị: Chương 6 Cây, cung cấp cho người đọc những kiến thức như: Khái niệm Cây; Các tính chất cơ bản của Cây; Cây khung của đồ thị; Cây khung nhỏ nhất. Mời các bạn cùng tham khảo! | CHƯƠNG 6 CÂY Tôn Quang Toại Khoa CNTT Đại học Ngoại ngữ Tin học Nội dung Khái niệm Cây Các tính chất cơ bản của Cây Cây khung của đồ thị Cây khung nhỏ nhất Khái niệm cây Định nghĩa Cây Tree Cây là Đồ̀ thị vô hướng liên thông và không có chu trình B E F B E F A A C D C D G1 G2 Khái niệm cây Định nghĩa Rừng Forest Rừng là đồ thị không có chu trình B G I L J A C F K D E H Nhận xét Rừng là đồ thị mà mỗi thành phần liên thông của nó là một cây. Các tính chất cơ bản của Cây Định lý Cho đồ̀ thị vô hướng G V E có n đỉnh. Các mệnh đề̀ sau tương đương 1 G là 1 cây 2 G không chứa chu trình và có n-1 cạnh 3 G liên thông và có n-1 cạnh 4 G liên thông và mỗi cạnh của nó điều là cầu 5 Giữa hai đỉnh bất kỳ của G được nối với nhau bởi đúng một đường đi duy nhất 6 G không chứa chu trình nhưng khi thêm vào một cạnh ta thu được đúng một chu trình Các tính chất cơ bản của Cây Sơ đồ chứng minh Chứng minh Các tính chất cơ bản của Cây Chứng minh Các tính chất cơ bản của Cây Chứng minh Các tính chất cơ bản của Cây Chứng minh Các tính chất cơ bản của Cây Chứng minh Các tính chất cơ bản của Cây Chứng minh Cây khung của đồ thị Định nghĩa Cây khung spanning tree của đồ̀ thị Một cây T gọi là cây khung cây bao trùm của đồ thị G V E nếu C D T V E F E E A C D B E C D A F A F B E B E Cây khung của đồ thị Định lý Cayley Số cây khung của đồ thị là a n 4 số cây khung là 4 16 d f b Ví dụ abc bcd cda dab c e abf acf bdf . A n 5 Số cây khung là 5 125 B C D E Cây khung của đồ thị Bài toán Cho G là đồ thị vô hướng liên thông hãy tìm 1 cây khung của đồ thị Lời giải Thuật toán tìm kiếm theo chiều sâu DFS Thuật toán tìm kiếm theo chiều rộng BFS Cây khung của đồ thị Tìm cây khung theo DFS void SpanningTree_DFS int u 1. Đánh dấu u đã viếng thăm 2. Xét mọi đỉnh v chưa được viếng thăm và kề u với từng đỉnh v đó T T u v DFS v Cây khung của đồ thị Tìm cây khung theo BFS void SpanningTree_BFS - Đánh dấu mọi đỉnh chưa viếng thăm - Đánh dấu u 0 đã viếng thăm - u while q - u - Tìm tất cả

• Toán học
• Bài giảng Lý thuyết đồ thị
• Lý thuyết đồ thị
• Cây khung của đồ thị
• Cây khung nhỏ nhất
• Đồ thị vô hướng
• 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
• Đồ 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