Cây Spanning tối thiểu: Thuộc tính Cut là gì?

Question

Tôi đã dành rất nhiều thời gian đọc các bài thuyết trình và sách giáo khoa trực tuyến về tài sản bị cắt của một cây bao trùm tối thiểu. Tôi không thực sự có được những gì nó giả sử để minh họa hoặc thậm chí lý do tại sao nó thực tế. Giả sử nó giúp xác định những gì cạnh để thêm vào một MST, nhưng tôi không thấy làm thế nào nó hoàn thành điều đó. Sự hiểu biết của tôi về tài sản cắt cho đến nay là bạn chia một MST thành hai tập con tùy ý. Bất kỳ trợ giúp ở đây? Cảm ơn!

Answer 1

Cắt một biểu đồ được kết nối là một tập hợp các cạnh tối thiểu mà việc loại bỏ biểu đồ tách thành hai thành phần (miếng). Thuộc tính cắt tối thiểu nói rằng nếu một trong các cạnh của vết cắt có trọng lượng nhỏ hơn bất kỳ cạnh nào khác trong vết cắt thì nó nằm trong MST. Để thấy điều này, giả sử rằng có một MST không chứa cạnh. Nếu chúng ta thêm cạnh vào MST, chúng ta sẽ có chu kỳ cắt giảm ít nhất hai lần, vì vậy chúng ta có thể phá vỡ chu trình bằng cách loại bỏ cạnh khác khỏi MST, do đó tạo một cây mới có trọng lượng nhỏ hơn, do đó mâu thuẫn với mức tối thiểu của MST.