Wieviele Verbindungen gibt es bei x Punkten?

[StefanDP]

Hallo.

Ich möchte berechnen, wieviele Möglcihkeiten es gibt um Streckennetze zwischen x Punkten zu erstellen. Dabei wird immer von einem Startpunkt ausgegangen, der definiert ist.
Von jedem Punkt dürfen beliebig viele Verbindungen ausgehen.

Beispiel: (A ist immer der Startpunkt)
Bei 2 Punkten (A, B) gibt es nur die eine Möglichkeit:

Code:

A-B

= 1 Möglichkeit

Bei 3 Punkten (A, B, C) gibt es die Möglichkeiten:

Code:

A-B
|
C

A-B-C

A-C-B

= 3 Möglichkeiten

Bei 4 Punkten (A .. D) gibt es:

Code:

B
|
A-C
|
D

A-B-D   A-B
|       |
C       C-D

A-B-C  A-B
|      |
D      D-C

A-C-B  A-C
|      |
D      D-B

A-B-C  A-B-C-D  A-B-D-C
  |
  D

A-C-B  A-C-B-D  A-C-D-B
  |
  D

A-D-B  A-D-B-C  A-D-C-B
  |
  C

= 16 Möglichkeiten

aber wie zum Teufel kann man das berechnen?

mitn bissl warscheinlichkeitslehren-rechnen hab ich schon n kleinen formelansatz:

für 2 punkte gibt es

Code:

1 * (1 über 1) = 1

(also ein startpunkt * ein von ein mögl. restpunkte)

für 3 punkte gibt es

Code:

1 * [ (2 über 2)
     +(2 über 1)*(1 über 1) ] = 3

(erklärung: ein startpunkt * (entweder: 2 von 2 mögl. restpunkten anfahren, [plus] oder: (1 von 2 mögl. restpunkten anfahren) * (1 von 1 mögl. restpunkten anfahren))

für 4 punkte gibt es
?? ich komm nichtmehr weiter, ich kapier die systematik nicht ganz :shock:


wär super wenn jmd das problem bzw. n lösungsansatz kennt!

PS: ich hab mit einem programm berechnet wieviel es geben muss (mit ner rekursiven fuktion)
dabei kommen folgende ergebnisse raus:
2 pkt = 1 mögl
3 pkt = 3 mögl
4 pkt = 16 mögl
5 pkt = 137 mögl
6 pkt = 1716 mögl
7 pkt = 29317 mögl
8 pkt = 650854 mögl
9 pkt = 18144065 mögl.

[Aenogym]

hi,

(schlagt mich, falls ich voll daneben liege)
ich glaube, für solche probleme gibt es die Fakultät.
die fakultät von 9 zum beispiel ist:

1*2*3*4*5*6*7*8*9 = 9!

also immer das produkt der zahlen von eins bis zur gegebenen zahl.

edit: okay. *schmerz* ;)

aenogym

[StefanDP]

*schlag* ;)

das mit fakultät wär dann richtig, wenn jeder punkt nur einen folgepunkt hat.
jedoch ist die anzahl der folgepunkte für jeden punkt beliebig

[Eichhoernchen]

es müsste für 3 so aussehen wenn man Fakultät benutzen will:

Delphi-Quellcode:

A-B-C
A-C-B
B-A-C
B-C-A
C-B-A
C-A-B

[faux]

Würde es nicht genaugenommen bei 2 2 möglichkeiten geben?

Code:

A-B
B-A

Denn wenn man das mathematisch berechnen will, wird man das berücksichtigen müssen...

[jfheins]

Frage: Ist das für ihn ein Unterschied ?

z.B. bei der Frage: wieviele Isomere gibt es für Heptan sind die Atome nicht nummeriert, und es ist dir egal in welcher Reihenfolge die sind ;)

[StefanDP]

A-B ist gleich wie B-A

man könnte es so sagen:

beginnen wir in einem beliebigen punkt.
von diesem punkt aus können jetzt beliebig viele verbindungen zu noch nicht benutzen punkten gemacht werden. (man kann diesen punkt jetzt z.b. mit 1 weiterem punkt verbinden, mit 2, mit 3 oder auch mit keinem.
und genaus gehts dann weiter, also von allen neuen endpunkten können wieder beliebig viele verbindungen gemacht werden

das ganze gibt dann wie gesagt keine route (punkt 1, punkt 2, punkt 3...) sondern ein netz

[Eichhoernchen]

er sagt ja, er hat nen fest definierten startpunkt, aber dann verstehe ich nicht so ganz wie das hier klappen soll:

Delphi-Quellcode:

A-B  //ist hier a der startpunkt??? dann breitet sich die reihe nach links und nach rechts aus!!!!
|
C

A-B-C

A-C-B

für mich sieht das so aus:

(A-B) = 1 ne möglichkeit:

Delphi-Quellcode:

A-B

(A-B-C) = 2

Delphi-Quellcode:

A-B-C
A-C-B

(A-B-C-D) = 6

Delphi-Quellcode:

A-B-C-D
A-B-D-C
A-C-B-D
A-C-D-B
A-D-C-B
A-D-B-C

EDIT: Sorry ich hab das letzte Posting net gesehen, das hier vergessen!!

[DGL-luke]

*räusper*

Zitat:

(A-B-C) = 2
A-B-C
A-C-B

fehlt da nicht b-a-c?

im übrigen kommen wir doch hier fast schon an permutationen ran - welche abfolgen der buchstaben A,B und C gibt es?

nun, die per-hand-methode: ABC,ACB,BAC,BCA,CAB,CBA - also immer einen anderen buchstaben vorne hin, die hinteren durchwechseln. wenn man alle hat (n² | n=Anzahl Werte??? würde hier stimmen, denn 3²=6 die doppeltzen rausstreichen - oder auch nicht, da die reihenfolge ja wichtig sein kann.

Bitte widerlegt mich, falls das nicht stimmt.

[rascalpo]

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:

Delphi-Quellcode:

Verbindungen := 0;
for i := 1 to n do Verbindungen := Verbindungen +(i - 1);

[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 :gruebel:
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

Delphi-Quellcode:

 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:

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:

Zitat von BlackJack

Zitat:

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:

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.

[rascalpo]

Zitat:

(n-1)*n/2

daran könnte durchaus was dran sein, denn

Delphi-Quellcode:

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);

Zitat:

es muss auch nicht die "dauer" möglichst kurz sein, sondern die gesamtsumme aller einzelverbindungen (also quasi die länge des netztes)

okay, was ist aber, wenn die Anzahl der Kanten immer gleich bleibt????
(Edit:) Also bei N Punkten, immer N-1 Kanten...

[alzaimar]

Och, da will ich auch mal meinen Senf zu geben:
1. Ob A-B = B-A ist, hängt von der Aufgabenstellung ab, wenn A z.B. auf einem Berg liegt, ist es sehr wohl wichtig.
2. Was hier gesucht wird ist die Anzahl von Spanning Trees eines Graphen. Vielleicht bringt das hier was
http://citebase.eprints.org/cgi-bin/...org:cs/0502038

[StefanDP]

@rascalpo: ja genau, das stimmt allerdings

also: bei n punkten gibt es genau n-1 kanten, wobei jedoch alle puntke durch ein zusammenhängendes netz verbunden sein müssen.

ich glaub wir sind schon ein minimales stück weitergekommen, hab aber trotzdem noch keine formel/ergebnis :)

@alzaimar: der link geht ins leere. :(

[Claas M]

Zitat:

Zitat von StefanDP

also: bei n punkten gibt es genau n-1 kanten, wobei jedoch alle puntke durch ein zusammenhängendes netz verbunden sein müssen.

Wenn du jeden Punkt mit den anderen verbindest, stimmt n*(n-1). Ergibt auch ein Gitter, zeichne es mal auf. So, wenn nun aber nicht zwischen A-B oder B-a unterschieden wird, musst du das ganze halbieren. Ich sähe keine andere Lösung bei deiner Beschreibund.

[rascalpo]

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 nächsten, manchmal aber auch 2 und manchmal 3 und vielleicht auch 4.
vom Anfangpunkt aus gesehen könntest du die Verbindungen nacheinander aufschreiben...
die Verbindung A-B-C-D-E würde 1 1 1 1 geschrieben werden
A-B-E-C-D: 1 1 1 1 // 1+1+1+1 = 4*1 = 4 = 5-1 = N-1
und davon gäbe es N! Möglichkeiten, wobei die Summe der einzelnen Verbindungen immer N-1 wäre.
weiter beispiele:

Delphi-Quellcode:

|      C         
|      |
|    A-B-D-E   1 2 1     = 4               B D F
|                                           \|/     N=9
|      C                                   A-C-E  // 1 7  = 8
|      |                                    /|\
|    A-B-D    1 3         = 4              G H I
|      |
|      E      
|

die Anzahl der möglichen Verbindungs-Kombinationen (nur Verbindungen! und immer nur eine weitergeführte richtung!) wäre erstmal, alle möglichen "Auflösungen" zu finden...
bei N=5
1 1 1 1 // hie 4! div 4! möglichkeiten
1 1 2 // hier wären 3! div 2! möglichkeiten....
1 3 // 2!
2 2 // 2! div 2!
4 // 1!...
// 4+3+1+1+1 = 10 Möglichkeiten...
bei N = 6
1 1 1 1 1 // 5! div 5!
1 1 1 2 // 4! div 3!
1 1 3 // 3! div 2!
1 2 2 // 3! div 2!
1 4 // 2!
2 3 // 2!
5 // 1!
// 1+4+3+3+2+2+1 = 16. ..
das nur mal so als anregung.

[StefanDP]

hm. es können aber theoretisch alle knoten weiterverfolgt werden.

ich hab jetzt glaub in fachsprache das was ich bereits implementiert hab:
das nennt sich glaub Minimaler Spannbaum (Minimal Spanning Tree) mit n Knoten und n-1 Kanten. (danke @alzaimar)
Dabei ist es ein ungerichteter zusammenhängender Graph.

Lauter neue Ausdrücke für mich, aber anscheinend ist es genau das was ich brauch.


Daraus resultierend hab ich jetzt noch ne 2te implementierung von so einem spanning tree, aber weiß aber immer noch nicht, wieso es genau x möglichkeiten gibt so einen geschlossenen spannbaum zu machen. :(

[runger]

Hallo,

such mal im Internet unter Graphentheorie. Dort kannst du alles nachlesen.
Dort wird dieses Thema behandelt.

Rainer

[runger]

Hallo

Graphentheorie

Dort findest du die Theorie dazu!

Rainer