Moin Leude,
Kurzer Kontext:
Vor kurzem musste ich für eine Uniaufgabe einen Algorithmus schreiben, der einen einfachen, ungewichteten und ungerichteten Graphen (im Sinne der Graphentheorie) mit \(N\) Knoten und \(M\) zufällig verteilten Verbindungen erzeugt.
Erste Idee: Eine zufällige Verbindung (d.h. zwei zufällige Knoten) ziehen und hinzufügen, falls sie noch nicht vorhanden ist. Ansonsten wird einfach geskippt. Das ganze wird wiederholt, bis alle \(M\) Verbindungen gesetzt wurden.
Da dieser Algorithmus mit einem höheren Verhältnis zwischen \(M\) und \(N\) immer schlechter wird, hatten wir uns eine andere Lösung überlegt, die im Endeffekt eine Laufzeit von \(M\) im best case und eine von \( \frac{N\cdot (N-1)}{2} \) (maximale Anzahl an Verbindungen in einem einfachen, ungerichteten Graphen) im worst case hat. Da hierbei die Laufzeit eine gleichverteilte Wahrscheinlichkeitsfunktion ist, ist der average case einfach \(\frac{N\cdot (N-1) - 2M}{4}\).
Jetzt würde ich gerne (aus Interesse) herausfinden, bei was für einem Verhältnis von \(M\) und \(N\) letzterer Algorithmus im average case besser wird. Dazu würde ich also gerne auch die Wahrscheinlichkeitsverteilung der Iterationen (bis alle Verbindungen gesetzt wurden) bei der ersten Idee berechnen.
Nun zur Frage:
Nach eifrigem Überlegen, bin ich zu folgender Wahrscheinlichkeitsverteilung gekommen:
Bei einem Graphen mit \(N\) Knoten und \(M\) hinzuzufügenden Verbindungen, ist die Wahrscheinlichkeit \(P( n )\) genau \(n\) Iterationen zu benötigen, um alle \(M\) Verbindungen zu setzen:
\[ P( n ) = \frac{(|E|_\text{max}-1)!}{|E|_\text{max}^{n-1}\cdot (|E|_\text{max}-M-1)!} \underbrace{\sum_{i_1=1}^{M-1}i_1 \sum_{i_2=i_1}^{M-1}i_2\:...\sum_{i_{n-M}=i_{n-M-1}}^{M-1}i_{n-M}}_{n-M\text{ nested sums}} \]
Wobei \(|E|_\text{max} = \frac{N\cdot (N-1)}{2}\) die maximale Anzahl an Verbindungen im Graphen ist.
Tja, da hab ich jetzt das Problem, dass nicht nur die Anzahl der Summen variabel ist sondern auch noch voneinander abhängen. Würden sie nicht voneinander abhängen, wäre das ganze "recht einfach", da könnte man sich nämlich das Multinomial Theorem zunutze machen und das Ding in ein Produkt einer Summe verpacken. So aber leider nicht. Ich hab das ganze testweise auch mal mit Rekursion so einprogrammiert, aber das Ding ist scheiße lahm.
Keine Ahnung, wie fit ihr in Mathe seid, aber hat einer von euch zufällig ne gescheite Idee, dass ich mir die Rekursion sparen kann? ^^
Mfg
Kurzer Kontext:
Vor kurzem musste ich für eine Uniaufgabe einen Algorithmus schreiben, der einen einfachen, ungewichteten und ungerichteten Graphen (im Sinne der Graphentheorie) mit \(N\) Knoten und \(M\) zufällig verteilten Verbindungen erzeugt.
Erste Idee: Eine zufällige Verbindung (d.h. zwei zufällige Knoten) ziehen und hinzufügen, falls sie noch nicht vorhanden ist. Ansonsten wird einfach geskippt. Das ganze wird wiederholt, bis alle \(M\) Verbindungen gesetzt wurden.
Da dieser Algorithmus mit einem höheren Verhältnis zwischen \(M\) und \(N\) immer schlechter wird, hatten wir uns eine andere Lösung überlegt, die im Endeffekt eine Laufzeit von \(M\) im best case und eine von \( \frac{N\cdot (N-1)}{2} \) (maximale Anzahl an Verbindungen in einem einfachen, ungerichteten Graphen) im worst case hat. Da hierbei die Laufzeit eine gleichverteilte Wahrscheinlichkeitsfunktion ist, ist der average case einfach \(\frac{N\cdot (N-1) - 2M}{4}\).
Jetzt würde ich gerne (aus Interesse) herausfinden, bei was für einem Verhältnis von \(M\) und \(N\) letzterer Algorithmus im average case besser wird. Dazu würde ich also gerne auch die Wahrscheinlichkeitsverteilung der Iterationen (bis alle Verbindungen gesetzt wurden) bei der ersten Idee berechnen.
Nun zur Frage:
Nach eifrigem Überlegen, bin ich zu folgender Wahrscheinlichkeitsverteilung gekommen:
Bei einem Graphen mit \(N\) Knoten und \(M\) hinzuzufügenden Verbindungen, ist die Wahrscheinlichkeit \(P( n )\) genau \(n\) Iterationen zu benötigen, um alle \(M\) Verbindungen zu setzen:
\[ P( n ) = \frac{(|E|_\text{max}-1)!}{|E|_\text{max}^{n-1}\cdot (|E|_\text{max}-M-1)!} \underbrace{\sum_{i_1=1}^{M-1}i_1 \sum_{i_2=i_1}^{M-1}i_2\:...\sum_{i_{n-M}=i_{n-M-1}}^{M-1}i_{n-M}}_{n-M\text{ nested sums}} \]
Wobei \(|E|_\text{max} = \frac{N\cdot (N-1)}{2}\) die maximale Anzahl an Verbindungen im Graphen ist.
Tja, da hab ich jetzt das Problem, dass nicht nur die Anzahl der Summen variabel ist sondern auch noch voneinander abhängen. Würden sie nicht voneinander abhängen, wäre das ganze "recht einfach", da könnte man sich nämlich das Multinomial Theorem zunutze machen und das Ding in ein Produkt einer Summe verpacken. So aber leider nicht. Ich hab das ganze testweise auch mal mit Rekursion so einprogrammiert, aber das Ding ist scheiße lahm.
Keine Ahnung, wie fit ihr in Mathe seid, aber hat einer von euch zufällig ne gescheite Idee, dass ich mir die Rekursion sparen kann? ^^
Mfg
Zuletzt bearbeitet:
