tailieunhanh - Chương II: Cây

Cây là đồ thị liên thông và không có chu trình | Khoa Công Nghệ Thông Tin Đại học Khoa học Tự nhiên CHƯƠNG II. CAY Định nghĩa ạ Cay la đô thị liên thông va không cô chu trình b Môt rừng p cay la môt đô thị gôm p thanh phan liên thông trông đô môi thanh phan liên thông la môt cay Ví du. Trông cac đô thị dừới đay thì G1 không la cay G2 va G3 la cay chu y định nghĩa chu trình cua đô thị cô hừớng trông chừơng I G1 Ghi chu. Định nghĩa cay ham y rang môi cay đêu không chứa khuyên cung không chừa canh sông sông. Định ly ve sự ton tai cac đỉnh treo Nêu môt cay T gôm n đỉnh vơi n 2 thì T chứa ít nhất hai đỉnh trêô Định ly ve cac định nghĩa tương đương Xêt môt đô thị G gôm n đỉnh cac điêu sau đay 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 nàô cua G thì nô không côn liên thông nữa . d Thêm môt canh nôi 2 đỉnh bất ky cua G thì G sê chừa môt chu trình duy nhất. ê G liên thông va cô n-1 canh f G không cô chu trình va cô 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 học Khoa học Tự nhiên Cho G X E là một đổ thị liên thông và T X F là một đổ thị bộ phận cua G. Neu T là cày thì T được gội là một cày toi đai cua G. Định ly sự ton tại cay tốì đại Mội độ thị liên thộng đêu cộ chưà ít nhất một cày tội đại Thuật toan tìm một cạy tốì đại của đo thị G Chộ G X E là một độ thị liên thộng gộm n đỉnh. Thuàt tộàn sàu đày chộ phêp tìm rà được một cày tội đài củà G. Bườcl. Chọn tùy ý v e X va khởi tạo V v T 0 Bưởc 2. Chọn we X V sao cho cô mọt cạnh ệ nao đô cùa G nôi w vởi mọt đỉnh trong V Bưởc 3. Gan V V u w va T T u ệ Bưởc 4. Nêù T đù n-1 phan tử thì dưng ngưởc lai lam tiệp tục bưởc 2. Cậy toì đại ngan nhất Định nghĩa Cho đo thị G X E . a Đo thị G đưởc gọi la co trọng nêu moi canh cùa G đưởc tưởng ứng vởi mọt sộ thực dưởng nghĩa la co mọt anh xa như saù L E------- IR ệ I----- L