C'è uno spanning tree minimo che non contenga il bordo ponderato min/max?

Question

se abbiamo un (arbitraria) collegato grafo non orientato G, i cui bordi presentano distinte pesi,

1. fa ogni MST di G contiene bordo minimo ponderata?
2. c'è un MST di G che non contiene il limite massimo ponderato?

Inoltre, sono più grato se qualcuno può dare un suggerimento delle cose chiave che è necessario tenere a mente quando si tratta di tali domande MST.

Questo è un problema di compiti a casa. Grazie.

Answer 1

c'è un MST di G che non contiene il limite massimo ponderato?

Ci può essere, ma non è necessario. Si consideri un grafo 4 vertice come segue:

[A]--{2}--[B] 
|   | 
|   | 
{1}  {3} 
|   | 
|   | 
[C]-{50}--[D] 

L'albero di copertura minimo costituito dall'insieme bordo {CA, AB, BD}. Il peso massimo del bordo è 50, lungo {CD}, ma non fa parte dell'MST. Ma se G fosse già uguale al proprio MST, allora ovviamente sarebbe contenere il proprio limite massimo.

ogni MST di G contiene il limite minimo ponderato?

Sì. Gli MST hanno un taglio proprietà. A cut è semplicemente una partizione dei vertici del grafico in due insiemi disgiunti. Per ogni taglio che si può fare, se il peso di un bordo in quel taglio è minore dei pesi degli altri bordi nel taglio, allora questo bordo appartiene a tutti gli MST nel grafico. Poiché hai garantito che i pesi dei bordi sono distinti, hai anche garantito che c'è un bordo che è più piccolo di tutti gli altri bordi.

Inoltre, sono più grato se qualcuno può dare un suggerimento delle cose chiave che è necessario tenere a mente quando si tratta di tali domande MST.

La soluzione migliore è ragionare su cose che utilizzano le proprietà degli MST in generale e tentare di costruire specifici controesempi che si ritiene possano dimostrare. Ho dato un'istanza di ogni linea di ragionamento sopra. A causa delle proprietà di taglio e ciclo, è sempre possibile determinare esattamente quali bordi si trovano in un MST, quindi è possibile testare sistematicamente ciascun bordo per determinare se è o meno nell'MST.

Answer 2

Per la prima domanda la risposta è no, e lo dimostra lo kruskal's algorithm. Seleziona sempre il bordo del costo minimo.

Per la seconda domanda la risposta è sì, ed è banale trovare un grafico esempio:

1 - 2 (cost 10) 
2 - 3 (cost 100) 
3 - 1 (cost 1000) 

Il terzo bordo non potrà mai essere selezionata in quanto introduce un ciclo. Quindi, in sostanza, se il bordo con il costo massimo creerebbe un ciclo se inserito nel MST, non verrà inserito.

Answer 3

Ogni MST di G contiene il limite minimo ponderato?

Sì. Supponiamo di avere un MST che non contenga il bordo del peso minimo. Ora l'inclusione di questo spigolo su MST darà come risultato un cycle. Ora ci sarà sempre un altro bordo nel cycle che può essere rimosso per rimuovere il ciclo e mantenere ancora il grafico (MST) connesso.

C'è un MST di G che non contiene il limite massimo ponderato?

Dipende dal grafico. Se lo stesso è un albero, è necessario includere tutti i suoi spigoli n-1 nello MST, pertanto non è possibile escludere il limite massimo del peso. Inoltre, se il limite di peso massimo è cut-edge in modo che la sua esclusione non si traduca mai in connettività, non è possibile escludere il limite massimo di peso. Tuttavia, se il limite di peso massimo fa parte di un cycle, è possibile escluderlo dallo MST.

Answer 4

Vedo che anche tu stai studiando per CSC263 attraverso il test 2009? (! Stesso qui)

Un altro modo di vedere che il minimo è sempre in MST è quello di guardare semplicemente a questo bordo minimo (lo chiamano e):

  e 
v1 ---------------- v2 

(presuppongo che questo ha connessioni ad altre vertici). Ora, per NON essere incluso nel MST finale significa che a un certo punto abbiamo, senza perdita di generalità, v1 nel MST ma non v2. Tuttavia, l'unico modo per aggiungere v2 senza aggiungere e sarebbe dire che l'aggiunta di v1 non ha aggiunto e alla coda (perché per definizione, e sarebbe in cima alla coda perché ha la priorità più bassa) ma questo contraddice il teorema della costruzione MST.

Quindi, in sostanza, è impossibile avere un fronte con il peso minimo non raggiunto in coda, il che significa che qualsiasi MST costruito lo avrebbe.