Für einen Graph alle Möglichkeiten berechnen

sambalmueslie

Hallo,
ich bin gerade am überlegen wie ich einen Graph automatisch berechnen kann.
Dabei gelten folgende Regeln:

es gibt einen Start- und einen Zielknoten
jeder Knoten hat zwei ausgehende(outgoing) Kanten und zwei eingehende(incoming) Kanten, außer Start- und Zielknoten. Die haben nur jeweils ein- bzw. ausgehende Kanten.
ein Knoten kann sich nicht mit sich selbst verbinden also nicht sein eigenes Ziel sein

Jetzt ist für mich die Frage wie ich da überhaupt vorgehe??
Hab mal überlegt, dass bei 4 Knoten (A,B,C,D) folgende Vorgehensweise möglich ist:

Start = A
Ende = D
Variante 1: A -> B
 Variante 11: B -> C
  Variante 111: C -> D
 Variante 12: B -> D
 ...
Variante 2: A -> C
 ...
Variante 3: A -> D

also für jeden Knoten einen so viele neue Graphen erzeugen, wie noch vorhandene Knoten da sind und dann das rekursiv durchführen.
Jetzt fehlt aber noch das jeder Knoten zwei aus- bzw. eingehende Kanten hat.

Geht sowas überhaupt?? Oder gibt es da eine elegantere Lösung??
Für Ideen und Hilfe bin ich sehr dankbar.

Gruß Oli

D-U-D-E

Kannst du ein Beispiel für deinen Flußgraphen aufmalen? Ich glaube, so wie du das machen willst geht das gar nicht, weil es Knoten geben müßte, die nur eine aus-/eingehende Kane haben.

edit:
Hab mich vertan, es geht doch.

Jester

Das geht schon, allerdings gibt es halt sehr sehr viele Möglichkeiten. Das heißt spätestens ab 10-20 Knoten ist vermutlich Schluß. Hast Du nicht noch andere Einschränkungen, wie Dein Netzwerk aussehen darf?

sambalmueslie

Jester schrieb:

Das geht schon, allerdings gibt es halt sehr sehr viele Möglichkeiten. Das heißt spätestens ab 10-20 Knoten ist vermutlich Schluß. Hast Du nicht noch andere Einschränkungen, wie Dein Netzwerk aussehen darf?

Weiteres Kriterium ist, dass jeder Knoten eine Entscheidung darstellt, die mit richtig oder falsch beantwortet wird. Dies kommt als Kantengewichte hinzu.
Es können keine zwei Knoten mit richtig und falsch verbunden werden.

Hm ich hab mir mal überlegt, dass ich die Anzahl der Knoten die zwischen Start- und Endknoten liegen vorgebe. Also quasi den kürzesten Weg, wenn alle Entscheidungen mit "richtig" beantwortet werden.

Aber vielleicht mal die Frage, wie ich das prinzipiell mache? Dann kann ich mir vielleicht auch noch ein paar Einschränkungen einfallen lassen.

Von der Form müsste das ganze doch auf eine "Zigarre" rauslaufen, weil Start- und Zielkonten nur 2 eingehende- bzw. ausgehende Kanten haben.

Gruß Oli

Jester

Suchst Du eigentlich wirklich alle Möglichkeiten, oder bist Du an der Aufzählung nur interessiert um die Graphen auf bestimmte Eigenschaften zu testen und dann ggf. zu verwerfen, bis Du eine Lösung hast, die auch Deine zusätzlichen Eigenschaften hat?

Falls letzteres der Fall ist kann ich Dir nur empfehlen zu versuchen den Graphen gleich richtig zu konstruieren. Es gibt viel zu viele von diesen Graphen um die alle aufzuzählen. Schon bei mehr als 4 Knoten gibt geht's los:

C                C
   /                /
  A                A-D
 / \              /
S   D     vs.    S
 \ /              \
  B                B-F
   \                \
    E                E

aber es könnten natürlich links auch die anderen beinchen von A bzw. B zusammengeschlossen sein und in der nächsten ebene hast du noch viel mehr knotenpaare für die du diese auswahl treffen kannst...

Beschreib doch mal was Du eigentlich genau machen willst. Klingt ein bißchen so als wolltest Du einen Entscheidungsbaum erstellen.

sambalmueslie

Hi,
danke für die Antwort.
Eigentlich suche ich nur eine Übersicht von Möglichkeiten um mir eine auszusuchen. Es geht also nicht um alle Möglichkeiten sondern nur um eine Auswahl. Hab gedacht, dass das vielleicht einfacher geht, wenn ich mir das berechnen lasse

Hab hier mal ein Beispiel erstellt:

Beispielgraph

Beispielgraph(Variante)

Das ganze sich auszudenken ist halt etwas knifflig ..

Gruß Oli

Jester

sambalmueslie schrieb:

Eigentlich suche ich nur eine Übersicht von Möglichkeiten um mir eine auszusuchen. Es geht also nicht um alle Möglichkeiten sondern nur um eine Auswahl. Hab gedacht, dass das vielleicht einfacher geht, wenn ich mir das berechnen lasse

Ich denke nicht, dass das der beste Weg ist. Wie gesagt gibt es sehr sehr viele von diesen Graphen, so dass das recht lange dauern dürfte die aufzuzählen. Wenn Du an irgendeinem interessiert bist, dann erstelle den doch zufällig. Nimm einen Knoten nach dem anderen (außer dem zielknoten), ziehe zufällig einen Knoten, der noch nicht 2 eingehende Kanten hat und verbinde in rot, zieh noch einen zufällig der noch keine 2 eingehenden kanten hat (evtl. den mit rot verbundenen rausnehmen) und verbinde in grün.

Insgesamt sollte sich dann ein zufällig generierter Graph mit den von Dir beschriebenen Eigenschaften ergeben.

sambalmueslie

Jester schrieb:

sambalmueslie schrieb:

Eigentlich suche ich nur eine Übersicht von Möglichkeiten um mir eine auszusuchen. Es geht also nicht um alle Möglichkeiten sondern nur um eine Auswahl. Hab gedacht, dass das vielleicht einfacher geht, wenn ich mir das berechnen lasse

Ich denke nicht, dass das der beste Weg ist. Wie gesagt gibt es sehr sehr viele von diesen Graphen, so dass das recht lange dauern dürfte die aufzuzählen. Wenn Du an irgendeinem interessiert bist, dann erstelle den doch zufällig. Nimm einen Knoten nach dem anderen (außer dem zielknoten), ziehe zufällig einen Knoten, der noch nicht 2 eingehende Kanten hat und verbinde in rot, zieh noch einen zufällig der noch keine 2 eingehenden kanten hat (evtl. den mit rot verbundenen rausnehmen) und verbinde in grün.

Insgesamt sollte sich dann ein zufällig generierter Graph mit den von Dir beschriebenen Eigenschaften ergeben.

Hm und wenn ich dann noch 20 "zufällige" Graphen generiert hab..
dann hab ich ja auch ne Auswahl. Das klingt gut ..
Dann werd ich mal versuchen, das so umzusetzen.
Danke. Wenn ich was heraushab werde ich berichten
Gruß Oli