Grafici bipartite con pesi minimi

cs.stackexchange https://cs.stackexchange.com/questions/128045

Domanda

Ho un grafico bipartite completo con set di nodi $ A={A_1, A_2, \ LDOTS, A_N \} $ e $ B={B_1, B_2, \ LDOTS, B_N \} $ . Ogni nodo ha un peso, $ v_i $ per $ a_i $ e $ w_i $ per $ B_i $ . Ogni nodo $ A_i $ è collegato a esattamente un nodo di $ B $ , dì $ B_J $ , tramite un bordo $ e_i $ , il cui peso è $ \ min (v_i, w_j) $ . Ora voglio trovare una mappatura one-to-one da $ a $ a $ B $ , di chi la somma dei pesi del bordo è il più piccolo possibile.

La mia idea è di ordinare $ v_i $ s sempre più e $ w_i $ s decreasellamente e poi trovare La somma di tutto $ \ min (v_i, w_i) $ dopo l'ordinamento. È corretto? Puoi dare una prova / disaccordo?

Ho eseguito simulazioni al computer per $ n= 5,6, \ ldots, 10 $ con pesi vertice casuali e non ha trovato alcun controesempio.

È stato utile?

Soluzione

È bello che tu abbia controllato la tua idea su alcuni campioni casuali.

.

Per capire perché la tua idea funziona, troviamo il caso più semplice ma non banale e poi dargli un'occhiata. Per semplicità e Wlog, il peso di un nodo verrà utilizzato per indicare quel nodo. Ad esempio, se $ a $ contiene un nodo con peso $ 42 $ , quel nodo sarà indicato come Nodo 42.

Il caso di $ n= 1 $ è banale.

Let $ n= 2 $ . Se capita di guardare a $ A={1, 2 \} $ e $ B={3, 4 \} $ , tuttavia, tuttavia scegliamo la mappatura, la somma sarà $ 1 + 2= 3 $ . Questo campione non apparentemente non illuminante.

Che ne dici di $ a={1, 3 \} $ e $ B={2,4 \ } $ ?

    .
  • Se colleghiamo 1 con 2 e 3 con 4, la somma è $ \ min (1,2) + \ min (3,4)= 1 + 3= 4 $ .
  • Se colleghiamo 1 con 4 e 3 con 2, la somma è $ \ min (1,4) + \ min (3,2)= 1 + 2= 3 $ .

Quindi questo è un esempio non banale. Ora dovremmo chiedere la domanda di base, Perché La seconda scelta produce una somma più piccola?

Per rispondere alla domanda, dovremmo osservare come vengono queste due somme. Nota che 1 appare in entrambe le somme. È quella coincidenza? Pensa per un momento e saprai che non lo è. 1 è il numero minimo di tutti i numeri. Quindi qualunque cosa sia collegata, sarà selezionato come il peso della connessione.

Ciò significa, qualunque sia collegato il numero 1, che è 3 in questo caso, quel numero mancherà da calcoli successivi, I.e., sarà "sprecato". Più grande è il "rifiuto", meno i numeri rimanenti saranno e quindi il peso inferiore la connessione rimanente produrrà, poiché funzione $ \ min (\ cdot, \ clot) $ < / span> sta diminuendo rispetto a entrambe le variabili. Quindi 1 dovrebbe essere collegato a un numero il più grande possibile. Questo è Perché 1 è collegato a 4 anziché 3 in modo da produrre la somma totale minima.

Nel caso di $ n= 2 $ , ci sono solo due scelte della mappatura. O il numero più piccolo in $ A $ è mappato al numero più piccolo in $ B $ , soprannominato "avanti Mappatura "o al numero più grande in $ B $ , soprannominato" mappatura inversa ". Per far sì che la mappatura producisca un peso totale più piccolo, dovremmo sempre scegliere la "mappatura inversa", in modo che un numero elevato venga sprecato (o, qual è lo stesso, un numero più piccolo verrà mantenuto da utilizzare.)

.

Per dimostrare che la tua idea è corretta, lo mostriamo per la prima volta per qualsiasi mappatura da $ a $ a $ B $ < / span>, c'è una mappatura che mappa $ \ min (a) $ a $ \ max (B) $ < / span> senza un peso totale maggiore. Supponiamo mappa $ f $ mappe $ \ min (a) $ a qualche $ B_J $ e alcuni numeri $ A_i $ a $ \ max (B) $ . Quindi possiamo fare un'altra mappa $ F '$ , che è lo stesso di $ f $ tranne per questi 4 Numero, $ F '$ Maps $ \ min (a) $ a $ \ max (B) $ e $ a_i $ a $ B_J $ . Poiché, come abbiamo mostrato sopra, per quattro numeri $ \ min (A), A_i $ e $ B_J $ , $ \ max (B) $ , abbiamo $$ \ min (\ min (A), \ max (B)) + \ min (A_i, B_J) \ Le \ min (\ min (A), B_J) + \ Min (A_I, \ MAX (B)), $$ Il peso totale della $ f '$ non è maggiore di quello della classe $ f $ .

Quindi sappiamo,

    .
  • Il peso totale minimo proviene da un mappatura che mappa $ \ min (a) $ a $ \ max (B ) $ .
  • Per tutti i mappature che mapano $ \ min (a) $ a $ \ max (B) $ , viene dal peso totale minimo deriva dallo stesso argomento, una mappatura che mappa il minimo dei numeri rimanenti in $ a $ (cioè il secondo numero minimo in < Span Class="Math-Container"> $ A $ ) al massimo dei numeri rimanenti in $ B $ (cioè il secondo numero minimo in $ B $ ).
  • per tutte le mappature che mapano
"> $ \ min (a) $ a $ \ max (B) $ e il secondo numero minimo in $ A $ al secondo numero massimo di $ B $ , il peso totale minimo proviene da una mappatura che mappa il terzo numero minimo in $ A $ al terzo numero massimo di $ B $ .
  • E così via, fino all'ultimo numero minimo in $ a $ è mappato all'ultimo numero massimo in $ B $ , cioè il numero massimo di $ A $ è mappato al numero minimo in $ B $ < / span>. $ \ Segnaliere $

    • potrebbe essere fornita una prova ancora più formale. Tuttavia, il ragionamento di cui sopra potrebbe essere più facile da capire. Dovrei, credo, convincere un normale umano.

    .

    Ecco un altro modo semplice per dimostrare la tua idea.

    Prima assumere tutti i numeri sono distinti. Dimosteniamo di Reductio ad Absurdum. Supponiamo che il peso totale minimo possa essere raggiunto da una mappatura $ G $ diverso dalla mappatura descritta nella tua idea. Quindi $ G $ deve contenere una sotto-mappatura che è una "mappatura in avanti", cioè, ci devono essere due numeri $ \ alfa_1 \ lt \ alfa_2 $ in $ a $ e due numeri $ \ beta_1 \ lt \ beta_2 $ in $ B $ tale che $ g (\ alpha_1)=beta_1 $ e < Span Class="Math-Container"> $ G (\ Alpha_2)=beta_2 $ .

    Ora possiamo fare un'altra mappatura $ G '$ che è la stessa di $ G $ Ovunque altrimenti tranne che la sotto-mappatura di $ g '$ su $ \ alfa_1 $ e $ \ alfa_2 $ è una "mappatura inversa", cioè, $ g '(\ alpha_1)=beta_2 $ e < Span Class="Math-Container"> $ G '(\ Alpha_2)=beta_1 $ . Ora possiamo, come prima, verificare che il peso totale di $ g '$ è più piccolo di quello della $ G $ < / span>, che contraddice il nostro assunto.

    Se tutti i numeri non sono distinti, useremo la tecnica di avvicinarsi per limiti. Perturbare tutti i numeri leggermente in modo che diventino distinti. Ora tutti i pesi saranno leggermente fuori dai loro pesi originali. Ciò significa che il peso totale ottenuto dalla tua idea non dovrebbe essere lontano dalla soluzione ottimale. Lascia che la perturbazione vada a zero, vediamo che è, infatti, la soluzione ottimale.

    .

    Potresti essere interessato a un problema simile, Come dimostrare l'algoritmo avido che minimizza la somma massima di un abbinamento .

    Altri suggerimenti

    Penso che la soluzione migliore qui sia usando l'algoritmo massimo del flusso massimo di costo su questo grafico.Se non lo sai, vai a leggere.Questo algoritmo è la soluzione più classica per questo tipo di problema.

    Autorizzato sotto: CC-BY-SA insieme a attribuzione
    Non affiliato a cs.stackexchange
    scroll top