tailieunhanh - Bài giảng về CÂY

Cây là đồ thị liên thông và không có chu trình. Một rừng p cây là một đồ thị gồm p thành phần liên thông, trong đó mỗi thành phần liên thông là một cây. Định nghĩa cây hàm ý rằng mọi cây đều không chứa khuyên cũng không chứa cạnh song song. | Định nghĩa Định nghĩa cây Cây lâ đồ thị liên thông vâ không co chu trình Môt rừng p cây lâ môt đô thị gôm p thânh phân liên thông trông đô môi thânh phân liên thông lâ môt cây Ghi chu Định nghĩâ cây hâm y râng môi cây đêu không chứâ khuyên cung không chứâ cạnh sông sông. Ly Thuyết Đo Thị - Cay - Khoa CNTT - Đai hoc KHTN 2 1 Định nghĩa Ví du. G và G không là cây G G1 Lý Thuyết Đo Thị - Cây - Khoa CNTT - Đại học KHTN 3 Định nghĩa Ví dUuGGVlâ và3 lâtìcà yà chai y chu hyTghnân chUhĩànChcCâìđô Lý Thuyết Đo Thị - Cây - Khoa CNTT - Đại học KHTN 2 Định ly vế sựtồn tai các đỉnh treo Nếu một cây T gồm n đỉnh với n 2 thì T chứa ít nhất hai đỉnh trếồ Chứng minh Ly Thuyết Đo Thị - Cáy - Khoa CNTT - Đái hoc KHTN 5 Định ly vế các định nghĩa tương đương Xết một đồ thị G gồm n đỉnh câc khang định sau đây lâ tương đương a Đồ thị G la cay. b Giữa hai đỉnh bất ky cua G tồn tai duy nhất một day chuyến nồi chung vơi nhau. c G liến thồng tồi tiếu nghĩa la G liến thồng va nếu xồa đi bất ky mồt canh naồ cua G thì nồ khồng cồn liến thồng nữa . Ly Thuyết Đo Thị - Cáy - Khoa CNTT - Đai hoc KHTN 6