tailieunhanh - Chương 2: 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. | Khoa Công Nghệ Thông Tin Đại hoc Khoa hoc Tự nhiên CHƯƠNG II. CAY Định nghĩa a Cay la đồ thị liên thong va khong co chu trình b Một rừng p cay la một đo thị gom p thanh phan liên thong trong đo moi thanh phan liên thong la mọt cay Ví du. Trong cac đo thị dừới đay thì G1 khong la cay G2 va G3 la cay chu y định nghĩa chu trình cua đo thị co hừớng trong chừơng I G1 Ghi chu. Định nghĩa cay ham y rang moi cay đêu khOng chứa khuyên cung khOng chừa canh song song. Định ly ve sự ton tai cac đỉnh treo Nêu mot cay T gom n đỉnh vơi n 2 thì T chứa ít nhất hai đỉnh trêo Định ly ve cac định nghĩa tương đương Xêt mọt đo thị G gom n đỉnh cac điêu sau đay từơng đừơng. a Đo thị G la cay. b Giừa hai đỉnh bất ky cua G ton tai duy nhat mot day chuyên nối chung vơi nhau. c G liên thong tối tiêu nghĩa la G liên thong va nếu xoa đi bat ky mọt canh nao cua G thì no khong con liên thong nữa . d Thêm mOt canh noi 2 đỉnh bất ky cua G thì G sê chừa mOt chu trình duy nhất. ê G liên thong va cO n-1 canh f G khOng cO chu trình va cO n-1 canh Cay toì đai cay phủ cay bao trùm cay khung Định nghĩa Chừơng II Cay trang I 1 Khoa Công Nghệ Thông Tin Đại hoc Khoa hoc Tự nhiên Cho G X E la một đồ thị liên thong va T X F la một đồ thị bo phạn cua G. Nêu T la cay thì T được gọi la mọt cay tối đai cua G. Định ly sự ton tại cay tốì đại Moi đo thị liên thong đêu co chưa ít nhat mot cay toi đai Thuật toan tìm một cạy tốì đại của đo thị G Cho G X E la mọt đo thị liên thong gom n đỉnh. Thuật toan sau đay cho phêp tìm ra được mOt cay toi đai cua G. Bưôcl. Chon tuy y v e X va khôi tao V v T 0 Bưôc 2. Chon we X V sao cho co mOt canh ê nao đo cua G nối w vôi mOt đỉnh trong V Bưôc 3. Gan V V u w va T T u ê Bưôc 4. Nêu T đu n-1 phan tử thì dưng ngược lai lam tiếp tuc bưôc 2. Cậy toì đại ngan nhất Định nghĩa Cho đo thị G X E . a Đo thị G được goi la co trong nếu moi canh cua G được tượng ứng vôi mOt so thực dượng nghĩa la co mOt anh xa như sau L E------- IR ê I----- L