Bài giảng Toán học tổ hợp và cấu trúc rời rạc: Chương 5 - Lê Văn Luyện

Bài giảng "Toán học tổ hợp và cấu trúc rời rạc - Chương 5: Cây" có cấu trúc gồm 4 phần cung cấp cho người học các kiến thức: Định nghĩa và tính chất, cây khung ngắn nhất, cây có gốc, phép duyệt cây. nội dung chi tiết. | Bài giảng Toán học tổ hợp và cấu trúc rời rạc: Chương 5 - Lê Văn Luyện Chương 5 CÂY lvluyen@ FB: Nội dung Định nghĩa và tính chất Cây khung ngắn nhất Cây có gốc Phép duyệt cây 2 1. Định nghĩa và tính chất Định nghĩa. Cây (tree) là đồ thị vô hướng, liên thông và không có chu trình B E B E F F A A C D C D G1 G2 G1 là cây, G2 không phải cây 3 Cây 4 Rừng Định nghĩa. Rừng (forest) là đồ thị vô hướng 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. 5 Rừng 6 Tính chất của cây Định lý: Cho đồ thị vô hướng T có n đỉnh. Khi đó các phát biểu sau là tương đương: 1) T là 1 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 nó đều là cầu 5) Giữa hai đỉnh bất kỳ của T có đúng một đường đi nối chúng với nhau 6) T 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 7 Hệ quả. a) Một cây có ít nhất 2 đỉnh treo b) Nếu G là một rừng có n đỉnh và có p cây thì số cạnh của G là m=n-p 8 Cây khung của đồ thị Định nghĩa: Một cây T được gọi là cây khung (hay cây tối đại, cây bao trùm) của đồ thị G=(V, E) nếu T là đồ thị con của G và chứa tất cả các đỉnh của G. Ví dụ. Cho đồ thị C D A F B E Hãy tìm cây khung của G? .

Không thể tạo bản xem trước, hãy bấm tải xuống
TỪ KHÓA LIÊN QUAN
TÀI LIỆU MỚI ĐĂNG
16    102    4    28-03-2024
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.