Mindest angeschlossenen Subgraphen einen gegebenen Satz von Knoten enthält,

Question

Ich habe eine ungewichtete, zusammenhängender Graph. Ich möchte einen zusammenhängenden Teilgraphen zu finden, die auf jeden Fall einen bestimmten Satz von Knoten enthält, und so einige Extras wie möglich. Wie kann dies erreicht werden?

Nur für den Fall, werde ich die Frage mit präziser Sprache neu formulieren. Es sei G (V, E) werden, um eine ungewichtete, ungerichtet, zusammenhängenden Graphen. Es sei N eine Teilmenge von V. seines Was ist der beste Weg, um die kleinsten zusammenhängenden Teilgraphen G ‚(V‘, E ‚) von G (V, E), so dass N ist eine Teilmenge von V‘ finden?

Annäherungen sind in Ordnung.

Answer 1

Ich kann nicht glauben, von einem effizienten Algorithmus, um die optimale Lösung zu finden, aber unter der Annahme, dass Ihre Eingabe Graph dicht ist, kann die folgende funktioniert gut genug:

1. Konvertieren Sie Ihre Eingabe Graph G(V, E) einem gewichteten Graph G'(N, D), wo N ist die Teilmenge von Eckpunkten Sie Abdeckung und D wollen, ist Abstände (Weglängen) zwischen den Scheitelpunkten in dem ursprünglichen Graphen entspricht. Dies wird „Kollaps“ alle Ecken Sie nicht in Kanten müssen.

2. Berechnen Sie den Mindest-Spanning-Tree für G'.

3. „Erweitern“ den minimalen Spanning Tree durch das folgende Verfahren: für jede Kante d in der minimalen Spanning-Tree, nehmen den entsprechenden Pfad in Graph G und fügen alle Knoten (einschließlich der Endpunkte) auf dem Weg zu der Ergebnismenge V' und alle Kanten auf dem Weg zu der Ergebnismenge E'.

Dieser Algorithmus ist einfach suboptimal Lösungen zu geben, zu Fall zu bringen. Beispielsfall: gleichseitiges Dreieck, wo es Vertices an den Ecken, in Mittelpunkten der Seiten und in der Mitte des Dreiecks, und die Kanten an den Seiten und von den Ecken zur Mitte des Dreiecks. Um die Ecken zu bedecken es ist genug, um den einzigen Mittelpunkt des Dreiecks zu holen, aber dieser Algorithmus könnte die Seiten wählen. Dennoch, wenn der Graph dicht ist, sollte es in Ordnung arbeiten.

Answer 2

Das ist genau das bekannte NP-hard Steiner Baum Problem. Ohne weitere Details darüber, was Ihre Instanzen aussehen, ist es schwer, Beratung zu einem geeigneten Algorithmus zu geben.

Answer 3

Die einfachste Lösung ist die folgende:

a) basierend auf mst: - zunächst alle Knoten von V sind in V‘ - bauen ein Minimum Spanning Tree des Graphen G (V, E) - es nennen T.
- Schleife. Für jedes Blatt v in T, die nicht in N, löschen v von V‘ist
- Wiederholungsschleife, bis alle Blätter in T sind in N.

b) eine andere Lösung ist die folgende - basierend auf kürzesten Wegen Baum
. - Pick beliebigen Knoten in N, nenne es V sei v eine Wurzel eines Baums T sein = {v}. - Entfernen v von N.

• Schleife: 1) wählen den kürzesten Pfad von jedem Knoten in T und einen beliebigen Knoten in N. der kürzeste Weg P: {v, ..., u}, wobei V in T und u in N. 2) jeder Knoten in p wird zu V‘. 3) jeder Knoten in p und n von N. gelöscht --- Wiederholungsschleife, bis N ist leer.

Zu Beginn des Algorithmus: Berechnung alle kürzesten Wege in G beliebigen bekannten effizienten Algorithmus.

Persönlich verwendet, ich diesen Algorithmus in einem meiner Papiere, aber es ist besser geeignet für verteilte Umgebungen. Sei N die Menge des Knoten sein, dass wir miteinander zu verbinden müssen. Wir wollen ein Minimum bauen angeschlossen dominierend G des Graphen gesetzt, und wir wollen für die Knoten in N. Priorität einzuräumen Wir geben jeden Knoten u eine eindeutige Kennung ID (u). Lassen wir W (u) = 0, wenn u in N ist, andernfalls w (1). Wir schaffen Paar (w (u), ID (u)) für jeden Knoten u.

• jeden Knoten u baut einen multiset Relaisknoten. Das heißt, eine Menge M (u) 1-hop neigbhors, so daß jedes 2-Hop-Nachbarn ist ein Nachbar zu mindestens einem Knoten in M ??(u). [Das Minimum M (u), desto besser ist die Lösung].

• u ist in V‘wenn und nur wenn: u hat die kleinste Paar (w (u), id (u)) unter allen seinen Nachbarn. oder U ist in dem M (v) ausgewählt wird, wobei v ein 1-Hop-Nachbarn von u mit dem kleinsten (w (u), ID (u)).

- der Trick, wenn Sie diesen Algorithmus in einer zentralisierten Weise auszuführen ist effizient zu sein bei der Berechnung der 2-Hop-Nachbarn. Das Beste, was ich von O bekommen konnte (n ^ 3) bis O (n ^ 2,37) durch Matrixmultiplikation.

-. Ich möchte wirklich wissen, was die Annäherung Ration dieser letzten Lösung

Ich mag diese Referenz für Heuristik von steiner Baum: Der Steinerbaum Problem, Hwang Frank; Richards Dana 1955- Winter-Pawel 1952

Answer 4

Sie könnten versuchen, folgendes zu tun:

1. Erstellen eines minimal Vertex-Cover für die N gewünschten Knoten.

2. Collapse diese möglicherweise nicht verbunden, Untergraphen in "großen" Knoten. Das heißt, für jeden Untergraphen, entfernt sie aus dem Graphen, und ersetzt ihn durch einen neuen Knoten. Rufen Sie diesen Satz von Knoten N'.

3. Starten Sie eine minimale Scheitel Abdeckung der Knoten in N'.

4. "auspacken" die Knoten in N'.

Nicht sicher, ob es gibt Ihnen eine Annäherung in einigen spezifischen gebunden oder so. Man könnte vielleicht sogar den Algorithmus Trick einige wirklich dumme Entscheidungen zu treffen.