Wieviele Verbindungen gibt es bei x Punkten?

[Eichhoernchen]

@DGL-luke: Ich dachte erst er wollte so ne art Lineare verlängerung wo immer A am anfang steht, aber dann hat er sein Posting geschrieben daher wären bei A-B-C, wenn a immer vorne stehen soll 2 möglich

hmmpf, bist du dir ganz sicher das deine funktion da richtige zahlen ausspuckt?


nochmal zum (A-B-C)

A-B-C
A-C-B

A-B
|
C

A-C
|
B


wäre das so wie da, dann würd ich glatt sagen das es:
(2!+3!)/2
n=Anzahl der Buchstaben i=2 und dann (summe(i!))/2
für n > 2
wobei n element N

Jedoch bin ich mir nicht ganz so sicher ob du das bei 4 Elementen richtig aufgezeichnet hast, wegen beispiel oben, nach deiner Definition find ich nämlich gilt meins oben dort als 4. Strecke! und dann würd auch das stimmen was ich da formel mäßig gemacht habe!

Aber irgendwie hab ich das Gefühl ich sollte im Pascalschen Dreieck nach der Lösung suchen

[Lannes]

Hallo,

geht das in die richtige Richtung
Permutationen, das Prog listet z. B. alle von "abcde" auf

[Eichhoernchen]

alle von abcde wäre ja 5! und das hat er ja gesagt ist es nicht!

[rascalpo]

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.

Delphi-Quellcode:

A     //

A-B     // 1

  A - B
|  \ /
    C   // 1 +2  = 3

A--B
|\/|   // (1 +2) + 3 = 6
|/\|
C--B

usw.
die Formel haben wir ja schon oben stehen

gut, aber wenn wir noch isomere dazuzählen wollen, wirds schwieriger...
A-B zählt wie D-C-A-B
|
C-D
aber wie siehts bei

Delphi-Quellcode:

A-B-C   // aus?
  | 
  D

sieht mir sehr danach aus:

Delphi-Quellcode:

|   A
   / \
     B
    / \
   D   C

Einem Binärbaum. Die Möglichkeiten vom Binärbaum sind leicht zu berechnen, weil der grosse Ähnlichkeiten mit Potenzmengen hat... also einfach
 2 ^ (n) n = Anzahl der Knoten

jetzt müsste man nur noch wissen, ob spiegelverkehrte Isomere einen Unterschied machen... also

Delphi-Quellcode:

|   A           A
   / \         / \
     B           B         // macht das hier nen Unterschied?
    / \         / \
   D   C       C  D

und wichtig wäre auch noch, wie Isomere gebildet werden könnten?

Stefan, was genau willst du eigentlich genau berechnen?

[StefanDP]

es hat was mit dem "problem des handelsreisenden" zu tun.
jedoch handelt es sich nicht um eine geschlossene rundstrecke sondern um ein netz.
es muss auch nicht die "dauer" möglichst kurz sein, sondern die gesamtsumme aller einzelverbindungen (also quasi die länge des netztes)

ich versuch mal den gedankengang für 4 punkte in eine grafik zu fassen:
Die Beschriftung bezieht sich immer auf den Startpunkt (A)
also:
von startpunkt A werden die restlichen 3 punkte gleichzeitig angefahren --> alle punkte erledigt, 1 möglichkeit

von startpunkt A werden 2 von 3 punkten angefahren (das gäb schonmal (3 über 2) = 6 möglichkeiten, nur um den startpunkt mit 2 weiteren punkten zu verbinden)
sind jetzt 2 punkte angefahren worden, kann der verbleibende punkt von beiden punkten angefahren werden.

von startpunkt A werden 1 von 3 punkten angefahren (das gibt genau (3 über 1) = 3 möglichkieten, nur um vom startpunkt zu einem anderen punkt zu gelangen.
von diesem punkt gibt es jetzt die möglichkeit, entweder direkt beide punkte anzufahren, oder erst den einen, dann den anderen, oder erst den anderen, dann den einen.

[edit=Admin]Bild als Anhang eingefügt. Mfg, Daniel[/edit]

[rascalpo]

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 beim Problem des Handelsreisenden. und, bin mir nicht sicher, jeder Baum mit N Knoten (=Punkten) hat genau N-1 Kanten (= Einzelverbindungen)???

[Claas M]

Also wenn ich es recht verstehe, müsste (n*(n-1))/2 die Lösung deines Problemes sein.

Das hatte ich mal für den Chemie-LK zusammengereimt um die Anzahl der Möglichkeiten einer Atomkollision eines Gases zu berechnen.

n ist die Anzahl deiner Punkte.

[BlackJack]

Zitat von Claas M:

Also wenn ich es recht verstehe, müsste (n*(n-1))/2 die Lösung deines Problemes sein.

Das hatte ich mal für den Chemie-LK zusammengereimt um die Anzahl der Möglichkeiten einer Atomkollision eines Gases zu berechnen.

n ist die Anzahl deiner Punkte.

könnte stimmen. von jedem der n punkte kann man noch zu n-1 punkten eine linie ziehen, und /2 komt zustande, weil es immer eine linie in 2 richtungen gibt (z.b. ist A->B und B->A ja die geliche linie)

[StefanDP]

Zitat von BlackJack:

Zitat von Claas M:

Also wenn ich es recht verstehe, müsste (n*(n-1))/2 die Lösung deines Problemes sein.

Das hatte ich mal für den Chemie-LK zusammengereimt um die Anzahl der Möglichkeiten einer Atomkollision eines Gases zu berechnen.

n ist die Anzahl deiner Punkte.

könnte stimmen. von jedem der n punkte kann man noch zu n-1 punkten eine linie ziehen, und /2 komt zustande, weil es immer eine linie in 2 richtungen gibt (z.b. ist A->B und B->A ja die geliche linie)

neeee, des ist net die lösung von meim problem
die aussage von blackjack ist net ganz richtig, von jedem punkt kann man nicht nur eine weitere verbindung machen, sondern soviel wie man will.

mit dem "baum" hat es was zu tun glaub ich, sieht mir danach aus.

aber einen reim kann ich mir immer noch nicht machen

...das ist mehr als linear, mehr als fakultät und mehr als expotentiell *verwirrt*

[BlackJack]

Zitat von StefanDP:

die aussage von blackjack ist net ganz richtig, von jedem punkt kann man nicht nur eine weitere verbindung machen, sondern soviel wie man will.

also willst du von einem punkt aus alle wege errechnen, durch die du alle punkte besuchen kannst?
weil (n-1)*n/2 errechnet die anzahl aller möglichen verbindungen zwischen n punkten, da bin ich mir relativ sicher.