Minimalne drzewo opinające: Czym dokładnie jest właściwość Wytnij?

Question

Spędzałem dużo czasu czytając prezentacje i podręczniki online na temat wyciętej właściwości minimalnego drzewa opinającego. Naprawdę nie rozumiem tego, co zilustrować, a nawet dlaczego jest to praktyczne. Podobno pomaga określić, które krawędzie dodać do MST, ale nie widzę, jak to osiągnąć. Dotychczasowe rozumienie właściwości wycinania polega na podzieleniu MST na dwa dowolne podzbiory. Jakąkolwiek pomoc tutaj? Dzięki!

Answer 1

Cięcie połączonego wykresu to minimalny zestaw krawędzi, których usunięcie powoduje oddzielenie wykresu na dwa elementy (części). Minimalna właściwość cięcia mówi, że jeśli jedna z krawędzi cięcia ma masę mniejszą niż jakakolwiek inna krawędź cięcia, to jest w MST. Aby to zobaczyć, załóżmy, że istnieje MST nie zawierający krawędzi. Jeśli dodamy krawędź do MST, otrzymamy cykl, który przecina cięcie co najmniej dwa razy, więc możemy przerwać cykl, usuwając drugą krawędź z MST, tworząc w ten sposób nowe drzewo o mniejszej wadze, tym samym zaprzeczając minimalności MST.