tailieunhanh - Một số vấn đề về thuật toán part 9

Tham khảo tài liệu 'một số vấn đề về thuật toán part 9', khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | . Bài toán cây bao trùm nhỏ nhất và thuật toán 193 Giả sử mỗi cạnh u v của G có trọng lượng w ụ v có thể ỉà số 0 hoặc một sô âm . Ta định nghĩa trọng ỉượng của cây bao trùm T là tổng trọng lượng của các cạnh của cây bao trùm này w T L w u v . cr Một cây bao trùm nhỏ nhất viết tắt là MST là cây bao trùm có trọng lượng nhỏ nhâ t. Hình SỐ cậy bao trùm của G yà cây baọ trùm nhỏ nhất là Ti Chú ý rằng cây bạo trùm nhỏ nhất không phải duy nhất nhưng đứng là nếu tất cả các cạnh có trọng lượng khác nhau thì MST sẽ khác nhau. Ví dụ cây T có trọng lựợng nhọ nhất hình . Tiếp cộn thuột toán tlm cày bao tràm nhò nhất Ta sẽ trình bày thuật toán tham cho việc tính cây bao trùm nhỏ nhất. Thuật toán tham được xây dựng trên cơ sỏ lặp lại lựa chọn trọng lượng nhỏ nhất giữa tất cả khả nẵng lựa chọn tại mỗi bước có tính chất địa 194 Chương 6. Phương pháp tham phương hoặc chủ quan . Đặc trưng quan trọng của thuật toán tham là luộn luôn chọn được không bao giờ không thể chọn. Để lạp được thuật toán ta nhắc lại một số tính chất của câỳ tự do. Bổ đề sau đây dễ đàng được chứng minh. Mênh để . Đôi với một cây tự do thì Cây tự do có n đỉnh thì có đúng n cạnh. Tồn tại duy nhâ t một dường đi giữa hai đỉnh bất kì của cây tự do. Lập thêm một cạnh bấikì của cây tự do tạo ra một vòng tròn duy nhất. Ngắt cạnh bấtkìcủa đường tròn vừa ỉập trả đồ thị về cây tự do. Cho G V E là đồ thị liên thông không định hướng và các cạnh của nó có trọng lượng. Trực giác đằng sau thuật toán tham tìm cây bao trùm nhỏ nhất là thực hiện trên tập con A các cạnh mạ khỏi đầu nó bằng trống và sau đó ta cho thêm vào môi cạnh một lần cho đêh khỉ A bằrig MST. Ta nói rằng một tập con A c E là có khảnăng nếu A tập con các cạnh của cây baọ trùm nhỏ nhất nàọ đó. Ta nói rằng một cạnh u v E Á là chắc chăn nếu AU a v ọọ khả năng. Nói cách khác w v chắc chắn chọn thêm vào sao cho A có thể mở rộng đốt cây bao trùm nhỏ nhất Chú ý là nếu A có khả năng thì không thể cố chu trình khép kín. Thuật toán tham là thực hiện .