sottografo connesso minimo contenente un dato insieme di nodi

Question

ho un pesato, grafo connesso. Voglio trovare un sottografo connesso che include sicuramente un certo insieme di nodi, e come alcuni extra possibili. Come può essere realizzato?

Nel caso in cui, io ribadire la questione usando un linguaggio più preciso. Sia G (V, E) sia una non ponderata, non orientato, grafo connesso. Sia N un sottoinsieme di V. Qual è il modo migliore per trovare il più piccolo sottografo connesso G '(V', E ') di G (V, E) in modo tale che N è un sottoinsieme di V'?

approssimazioni sono bene.

Answer 1

Non riesco a pensare a un algoritmo efficiente per trovare la soluzione ottimale, ma supponendo che il grafico di ingresso è denso, di seguito potrebbe funzionare abbastanza bene:

1. Convertire la vostra G(V, E) grafo di input a un G'(N, D) grafo pesato, dove N è il sottoinsieme di vertici che si vogliono coprire e D viene distanze (lunghezze del percorso) tra i vertici corrispondente nel grafico originale. In questo modo "collasso" tutti i vertici non è necessario in bordi.

2. Calcola il minimo spanning tree per G'.

3. "espandere" il minimo albero di copertura secondo la seguente procedura: per ogni d bordo nella struttura di copertura minimo, prendere il percorso corrispondente grafico G e aggiungere tutti i vertici (inclusi i punti finali) sul percorso al risultato set V' e tutti i bordi del percorso del E' set di risultati.

Questo algoritmo è facile da scattare fino a dare soluzioni non ottimali. caso di esempio: triangolo equilatero dove ci sono vertici agli angoli, in punti medi dei lati e nel mezzo del triangolo, e bordi lungo i lati e dagli angoli al centro del triangolo. Per coprire gli angoli è sufficiente scegliere il punto di mezzo singolo del triangolo, ma questo algoritmo potrebbe scegliere i lati. Tuttavia, se il grafico è denso, dovrebbe funzionare OK.

Answer 2

Questo è esattamente il noto Steiner Albero problema. Senza ulteriori dettagli su ciò che i vostri casi assomigliano, è difficile dare consigli su un algoritmo appropriato.

Answer 3

Le soluzioni più semplici sarà il seguente:

a) sulla base di MST:    - Inizialmente, tutti i nodi di V sono in V'    - costruire un minimo spanning tree del grafo G (V, E) - chiamare T.
   - ciclo:. Per ogni foglia v in T che non è in N, v Eliminare dal V'
   - ciclo di ripetizione fino a quando tutte le foglie in T sono in N.

b) un'altra soluzione è il seguente - in base a più breve albero percorsi
.    - scegliere qualsiasi nodo N, chiamano V, Sia V una radice di un albero T = {v}.    - Rimuovere v da N.

• ciclo: 1) selezionare il percorso più breve da qualsiasi nodo T e qualsiasi nodo N. minor percorso p: {v, ..., u} dove v è in T e U è in N.  2) ogni nodo p viene aggiunto V'.  3) ogni nodo p in N viene eliminato da N. --- ripetizione ciclo finché N è vuoto.

All'inizio dell'algoritmo: calcolare tutti i percorsi più brevi in ??G utilizzando qualsiasi algoritmo efficiente noto.

Personalmente, ho usato questo algoritmo in una delle mie carte, ma è più adatto per ambienti distribuiti. Sia N l'insieme dei nodi che abbiamo bisogno di interconnessione. Vogliamo costruire una minima di collegamento che domina set del grafo G, e vogliamo dare la priorità per i nodi in N. Diamo ogni nodo u un identificatore univoco id (u). Lasciamo w (u) = 0 se u è in N, altrimenti w (1). Creiamo coppia (w (u), id (u)) per ogni nodo u.

• ogni nodo u costruisce un nodo di trasmissione multinsieme. Cioè, un insieme M (u) di neigbhors 1-hop tale che ciascun vicino 2-hop è un vicino ad almeno un nodo M (u). [Minimo M (u), migliore è la soluzione].

• U è in V' se e solo se: u ha la coppia più piccolo (w (u), ID (u)) fra tutti i suoi vicini. oppure u è selezionato nel M (v), dove v è un vicino di casa 1-hop di u con il più piccolo (w (u), ID (u)).

- il trucco quando si esegue questo algoritmo in modo centralizzato è quello di essere efficace nel calcolo vicini 2-hop. La migliore ho potuto ottenere da O (n ^ 3) è O (n ^ 2,37) per la moltiplicazione di matrici.

-. Ho davvero voglia di sapere che cosa è la razione approssimazione di quest'ultima soluzione

Mi piace questo riferimento per l'euristica di albero di Steiner: Il problema dell'albero di Steiner, Hwang Frank; Richards Dana 1955- inverno Pawel 1952

Answer 4

Si potrebbe provare a fare quanto segue:

1. Creazione di un minimo vertici copertura per i nodi N desiderato.

2. Chiudi questi, eventualmente non connessi, sub-grafici in "grandi" nodi. Cioè, per ogni sub-grafico, rimuoverlo dal grafico, e sostituirlo con un nuovo nodo. Chiamare questo insieme di nodi N'.

3. Do un minimo vertici copertura dei nodi in N'.

4. "Estrarre" i nodi N'.

Non è sicuro se sia o non ti dà un'approssimazione all'interno di alcuni specifici vincolati o giù di lì. Si potrebbe forse anche ingannare l'algoritmo di prendere alcune decisioni davvero stupide.