sottografo con connessione minima contenente un determinato set di nodi

Question

Ho un grafico collegato non ponderato. Voglio trovare un sottografo connesso che includa sicuramente un certo insieme di nodi e il minor numero possibile di extra. Come potrebbe essere realizzato?

Nel caso, ripeterò la domanda utilizzando un linguaggio più preciso. Sia G (V, E) un grafo connesso non orientato, non orientato. Sia N un sottoinsieme di V. Qual è il modo migliore per trovare il sottografo più piccolo G '(V', E ') di G (V, E) tale che N sia un sottoinsieme di V'?

Le approssimazioni vanno bene.

Answer 1

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

1. convertire il vostro grafo di input G(V, E) ad una ponderata grafico G'(N, D), dove N è il sottoinsieme di vertici che si desidera coprire e D è le distanze (lunghezze del percorso) tra i vertici corrispondenti nel grafico originale. Ciò "collassa" tutti i vertici di cui non hai bisogno nei bordi.

2. Calcolare lo spanning tree minimo per G'.

3. "Expand", la copertura minimo albero mediante la seguente procedura: per ogni fronte d nella copertura minimo albero, prendere il percorso corrispondente nel grafico G e aggiungere tutti i vertici (compresi endpoint) sul percorso al risultato impostare V' e tutti i bordi nel percorso del set di risultati E'.

Questo algoritmo è facile da inciampare per fornire soluzioni subottimali. Esempio di caso: triangolo equilatero dove ci sono vertici agli angoli, a metà dei lati e al centro del triangolo, e bordi lungo i lati e dagli angoli al centro del triangolo. Per coprire gli angoli è sufficiente scegliere l'unico punto centrale del triangolo, ma questo algoritmo potrebbe scegliere i lati. Tuttavia, se il grafico è denso, dovrebbe funzionare correttamente.

Answer 2

Si potrebbe provare a fare quanto segue:

1. Creazione di un minimal vertex-cover per i nodi desiderati N.

2. Comprimi questi sotto-grafici, probabilmente non collegati, in nodi "grandi". Cioè, per ogni sotto-grafico, rimuoverlo dal grafico e sostituirlo con un nuovo nodo. Chiama questo set di nodi N'.

3. Fare una copertura vertice minima dei nodi in N'.

4. "Disimballare" i nodi in N'.

Non è sicuro se sia o non ti dà un'approssimazione all'interno di alcuni specifici legati o giù di lì. Forse potresti persino ingannare l'algoritmo per prendere alcune decisioni davvero stupide.

Answer 3

Questo è esattamente il noto problema NP-hard Steiner Tree.Senza ulteriori dettagli su come appaiono le tue istanze, è difficile dare consigli su un algoritmo appropriato.

Answer 4

Le soluzioni più semplici saranno i seguenti:

a) sulla base MST: - inizialmente, tutti i nodi di V sono in V' - costruire un albero di copertura minimo del grafo G (V, E) - chiamatelo T.
- loop: per ogni foglia v in T che non è in N, cancella v da V '.
- ripetere il ciclo finché tutte le foglie in T sono in N.

b) un'altra soluzione è la seguente - basata su albero dei percorsi più breve.
- seleziona qualsiasi nodo in N, chiamalo 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 eu è in N. 2) ogni nodo in p viene aggiunto a V '. 3) ogni nodo in p in N viene cancellato da N. --- ripetere il ciclo finché N non è vuoto.

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

Personalmente, ho usato questo algoritmo in uno dei miei documenti, ma è più adatto per ambienti distribuiti. Sia N l'insieme di nodi che dobbiamo interconnettere. Vogliamo costruire un insieme di dominanti connessi al minimo del grafico G, e vogliamo dare la priorità ai nodi in N. Diamo a ciascun nodo u un identificativo univoco id (u). Lasciamo w (u) = 0 se si è 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 nebulizzatori 1-hop tale che ogni vicino 2-hop è un vicino ad almeno un nodo in M ​​(u). [il minimo M (u), migliore è la soluzione].

• u è in V 'se e solo se: u ha la coppia più piccola (w (u), id (u)) tra tutti i suoi vicini. o u è selezionato in M ​​(v), dove v è un vicino 1-hop di u con il più piccolo (w (u), id (u)).

- il trucco quando si esegue questo algoritmo in modo centralizzato è di essere efficienti nell'elaborare i vicini 2-hop. Il meglio che ho potuto ottenere da O (n^3) è O (n^2.37) per moltiplicazione di matrice.

- Vorrei davvero sapere qual è la razione di approssimazione di quest'ultima soluzione.

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