Pfad in Graph finden

Wissenschaft Mathematik
#1

Ich habe 3 (oder mehr) Mengen von Knoten eines ungerichteten Graphen.

Beispiel:
Knoten, die untereinender NICHT verbunden sind:
{A,B,C},{D,E,F},{G,H,I}

Es gibt aber Verbindungen (Kanten) zwischen diesen Knotenmengen.

Beispiel:

A+D,A+G,D+G

Frage: kann ich in Polynomzeit feststellen, ob ein Pfad von der
ersten Knotenmenge über die zweite zur dritten existiert?

Beispiel:
Angenommen, es existieren die Kanten:

A+D,A+G,D+G

so gibt es einen Pfad von A über D nach G, und auch direkt von
A nach G.

Angenommen, es existieren AUSSCHLIEßLICH die Kanten:

A+D,A+H,D+G

So gibt es eine Kante von der ersten Knotenmenge zur dritten
(A+H), aber nicht eine passende Verbindung in der zweiten
Knotenmenge.

Habe viel gegoogelt und in Wikipedia gelesen, ich denke,
der Graph, den ich meine, heißt Turan-Graph
(http://de.wikipedia.org/wiki/Tur%C3%A1n-Graph#Der_Tu…),
aber ich kann dort keine Antwort auf meine Frage finden.

Danke und Gruß

#2

Hallo,

man könnte wie folgt an die Sache herangehen:
Man weise allen Knoten, die über eine oder mehrere Kanten verbunden sind, denselben numerischen Wert zu (-> Index). Das geht mit einer Union-Find-Datenstruktur praktisch in linearer Zeit (bezüglich der Kantenzahl).
Ziel ist es nun, einen Index zu finden, der in allen Mengen vorhanden ist. Sprich die Schnittmenge der Indexmengen. Mit entsprechenden Datenstrukturen (z.B. Hash-Mengen) ist diese Aufgabe auch in polynomieller Zeit lösbar.
Wenn die gefundene Schnittmenge nicht leer ist, gibt es Kanten, die alle Teilmengen miteinander verbinden.

Nico