Spanning tree minimo: cos'è esattamente la proprietà Cut?

Question

Ho trascorso molto tempo a leggere presentazioni online e libri di testo sulle proprietà di taglio di un albero di copertura minimo. In realtà non capisco cosa debba illustrare o perché sia ​​pratico. Presumibilmente aiuta a determinare quali bordi aggiungere a un MST, ma non riesco a vedere come lo realizza. La mia comprensione delle proprietà di taglio finora è che hai diviso un MST in due sottoinsiemi arbitrari. Qualche aiuto qui? Grazie!

Answer 1

Un taglio di un grafico collegato è un insieme minimo di bordi la cui rimozione separa il grafico in due componenti (pezzi). La proprietà di taglio minimo dice che se uno dei bordi del taglio ha un peso inferiore a qualsiasi altro bordo nel taglio, allora è nel MST. Per vedere questo, supponiamo che ci sia un MST che non contiene il bordo. Se aggiungiamo il bordo al MST otteniamo un ciclo che attraversa il taglio almeno due volte, in modo che possiamo interrompere il ciclo rimuovendo l'altro bordo dal MST, rendendo così un nuovo albero con un peso minore, contraddicendo così la minimalità del MST.