Bài giảng Toán rời rạc: Chương 6 Cây cung cấp cho người học những kiến thức như: Các định nghĩa và tính chất; Các ứng dụng của cây; Cây khung; Cây khung nhỏ nhất. Mời các bạn cùng tham khảo để nắm chi tiết nội dung của bài giảng! | CHƯƠNG 6 CÂY Nguyễn Quỳnh Diệp diepnq@ 1 Nguyễn Quỳnh Diệp NỘI DUNG Các định nghĩa và tính chất Các ứng dụng của cây Cây khung Cây khung nhỏ nhất Toán rời rạc Nguyễn Quỳnh Diệp 2 . CÁC ĐỊNH NGHĨA VÀ TÍNH CHẤT Toán rời rạc Nguyễn Quỳnh Diệp 3 CÂY Định nghĩa 1 Cây là một đồ thị vô hướng liên thông và không có chu trình đơn Ví dụ Toán rời rạc Nguyễn Quỳnh Diệp 4 CÂY Ví dụ Đồ thị nào sau đây là cây Đồ thị không có chu trình đơn và không liên thông gọi là rừng. Toán rời rạc Nguyễn Quỳnh Diệp 5 CÂY Định lí 1 Một đồ thị vô hướng là một cây nếu giữa mọi cặp đỉnh của nó luôn tồn tại đường đi đơn duy nhất. Định nghĩa 2 Cây có gốc là cây có một đỉnh được gọi là gốc và mọi cạnh có hướng từ gốc đi ra. Toán rời rạc Nguyễn Quỳnh Diệp 6 CÂY Ví dụ Toán rời rạc Nguyễn Quỳnh Diệp 7 MỘT SỐ THUẬT NGỮ Nếu v là đỉnh khác gốc Cha của v là đỉnh u duy nhất sao cho có 1 cạnh hướng từ u đến v. Khi đó u gọi là cha của v v gọi là con của u. Các đỉnh có cùng cha gọi là anh em. Toán rời rạc Nguyễn Quỳnh Diệp 8 MỘT SỐ THUẬT NGỮ Tổ tiên của một đỉnh khác gốc là các đỉnh trên đường đi từ gốc tời đỉnh này tức là cha của nó ông của nó cho tới khi đến gốc . Con cháu của đỉnh v là các đỉnh có v như tổ tiên Toán rời rạc Nguyễn Quỳnh Diệp 9 MỘT SỐ THUẬT NGỮ Các đỉnh của cây gọi là lá nếu nó không có con Các đỉnh có con gọi là đỉnh trong Toán rời rạc Nguyễn Quỳnh Diệp 10 MỘT SỐ THUẬT NGỮ Nếu a là đỉnh của 1 cây thì cây con với gốc a là đồ thị con của cây đang xét bao gồm a và các con cháu của nó cùng với các cạnh liên thuộc với các con cháu của a. Toán rời rạc Nguyễn Quỳnh Diệp 11 CÂY m-phân Định nghĩa 3 Cây có gốc được gọi là cây m-phân nếu tất cả các đỉnh trong của nó không có hơn m con. Cây được gọi là m-phân đầy đủ nếu mọi đỉnh trong có đúng m con. Khi m 2 ta có cây nhị phân Toán rời rạc Nguyễn Quỳnh Diệp 12 CÂY CÓ GỐC Cây có gốc được sắp Cây có gốc được sắp có thứ tự là cây có gốc mà trong đó các con của mỗi đỉnh trong được sắp xếp theo một thứ tự nhất định. Toán rời rạc Nguyễn Quỳnh .
