Forum: Programmieren allgemein
by rascalpo,
23. Aug 2005
hm.. dieses Problem hat irgendwie Ähnlichkeiten zu MISSISSIPPI (Permutation aus einer Menge mit Wiederholung..)
also, mal angenommen, bei einem Knoten existieren zwar mehrere Verbindungen, aber nur eine davon wird weiterverfolgt(so wie bei deiner Skizze das untere Beispiel A-C-E-F)
und wie immer hat er bei N Knoten genau N-1 Kanten.
und manchmal hat ein Punkt nur eine Verbindung zum...
Forum: Programmieren allgemein
by rascalpo,
23. Aug 2005
daran könnte durchaus was dran sein, denn
1 + 2 + 3 + 4 + ... + (n-1) + n = (n-1)*n div 2
//ist schliesslich (fast) das gleiche wie
Verbindungen := 0;
for i := 1 to n do Verbindungen := Verbindungen +(i - 1);
okay, was ist aber, wenn die Anzahl der Kanten immer gleich bleibt????
Forum: Programmieren allgemein
by rascalpo,
23. Aug 2005
hm...der Umfang vom Problem des Handelsreisenden wird normalerweise mit N! (N = die Anzahl der zu besuchenden Städte) beschrieben. Der Handelsreisende hat aber immer nur die Möglichkeit in eine einzige Richtung zu reisen...
Wenn ich das jetzt richtig verstanden hab: ALLE Punkte sind miteinander verbunden und öhm, wenn ich mich nicht irre, nennt man das einen Baum(Graphentheorie), vor allem...
Forum: Programmieren allgemein
by rascalpo,
23. Aug 2005
also, wenn ein Knoten beliebig viele Verbindungen(EDIT,ähem) haben darf, dann kommen jedes mal so viele mögl. verbindungen hinzu, wie schon punkte da waren.
A //
A-B // 1
A - B
| \ /
C // 1 +2 = 3
Forum: Programmieren allgemein
by rascalpo,
22. Aug 2005
also, wenn jeder "Knoten" maximal zwei Verbindungen haben kann, dann kann man es bei N Knoten mit N! berechnen.
Jeder Knoten hat aber maximal 3 Verbindungen.
Falls es einen Knoten gibt, der bevorzugt wird, und die Reihenfolge eine Rolle spielt, gibt es den Binärbaum (Wikipedia). Dieser is aber ein Sonderfall.
Falls es beliebige Anzahl (n) von Knoten gibt:
Verbindungen := 0;
for i := 1...
