Wieviele Verbindungen gibt es bei x Punkten?

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