Das Problem:
Sei G = (V, E) ein gerichteter Graph auf n & gt; = 3 Ecken mit m Kanten. Die Eckenmenge V enthält drei spezielle Ecken a, v und b. Suchen Sie einen einfachen Pfad von a nach b über v, falls vorhanden. (Ein einfacher Pfad ist ein Pfad ohne wiederholte Scheitelpunkte.)
Ich glaube, dieses Problem sollte / kann mit einem Max-Flow-Algorithmus gelöst werden, aber ich bin mir nicht sicher, wie. Es erinnert mich an einen Max-Flow-Algorithmus mit mehreren Quellen, bei denen die Kanten die Kapazität 1 haben. Wer weiß, wie das Problem auf den maximalen Flussalgorithmus reduziert werden kann?
Wenn ich Vertex b als Senke setze, kann ich nicht sicher sein, ob es v enthält. Wenn ich v als Senke einstelle, wie gehe ich weiter, wenn v erreicht wird?
Folgendes sollte funktionieren:
finde alle minimalen Pfade von a bis v , die keinen Vertex b enthalten. Sie können diese durch (z. B.) ein DFS in der Grafik ohne den Vertex b erhalten. Wir sagen, dass ein a-v -path p minimal ist, wenn kein anderer a-v -path p' nur Scheitelpunkte von p enthält.
Versuchen Sie für jeden minimalen a-v -Pfad, einen Pfad von v bis b zu finden, der Scheitelpunkte ignoriert, die bereits zum a-v -path gehören. Wenn Sie so etwas finden, sind Sie fertig.
Anmerkung: Beachten Sie, dass die Anzahl der Pfade exponentiell wachsen könnte, aber wie ich in meinem Kommentar darauf hingewiesen habe, scheint zumindest die verallgemeinerte Version dieses Problems auf den TSP reduzierbar zu sein, was wahrscheinlich ist sehr schwierig.
Dies ist gleichbedeutend mit der Frage, ob ein Graph einen zu einem gerichteten Pfad mit drei Stützpunkten homogenen Untergraphen enthält (ein Muster ist ein Graph auf einigen der Eckpunkte des Eingangsgraphen, und ein Untergraph ist homemorph zu einem Muster, wenn Kanten des Muster kann auf einfache, paarweise vertexfreie Pfade des Untergraphen abgebildet werden). Es wurde von Fortune, Hopcroft und Wyllie nachgewiesen, dass der gelenkte Subgraph-Homöomorphismus NP- ist. hart für fast alle festen Muster, einschließlich dieser. Das Problem ist daher NP-schwer und kann nicht durch Fließverfahren gelöst werden, außer P = NP.
Die ungerichtete Version kann jedoch auf den maximalen Fluss reduziert werden, indem a und b die Quelle und v die Senke sind.