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.