Algoritmo di teoria di Graphy per minimizzare le aree di connessione con i limiti condivisi

Question

Ho un grafico ponderato di "penne animali" multiple con ogni penna con almeno 3 spigoli/punti e almeno due penne. Devo calcolare i bordi ponderati minimi da rimuovere per collegare tutte le penne (è possibile collegarle rimuovendo i bordi esterni non collegati ad altre penne).

Qualcuno può consigliare un algoritmo o un processo con cui potrei avvicinarmi alla ricerca delle pareti pesate minime da rimuovere. Stavo pensando all'algoritmo di Prim, ma non sono nemmeno del tutto sicuro di come potrei applicarlo.

Questo è problema S4 su http://cemc.math.uwaterloo.ca/contests/computing/2010/stage1/seniorEn.pdf

Non voglio la risposta solo alcuni direzione su come avvicinarsi

Answer 1

Sei nella giusta direzione.

modello il problema come un grafo non orientato G=(V,E) dove V = { all pens }, E = { (u,v) | there is a wall between u and v } con w((u,v)) = cost of wall between u and v

Al fine di "collegare tutte le penne" - che in realtà sono alla ricerca di un sottografo: G'=(V,E') tale che il sub grafo G' sarà collegato [ C'è un percorso tra ogni due nodi], e il costo dei muri in E 'è minimo.

Per ottenere questo al minimo costo - stai cercando Minimum Spanning Tree. [È facile vedere che hai davvero bisogno di un albero - perché ogni bordo in più dopo aver creato l'albero è ridondante e può essere rimosso senza danneggiare la connettività del grafico - o nel termine del problema - puoi ripristinare un muro e le penne rimanere in contatto]

Due possibili algoritmi che ti porterà il MST sono Prim e Kruskal