Zusammenhängender Zufallsgraph < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Zeigen Sie wie man einen zusammenhängenden Zufallsgraphen erzeugt. Das bedeutet, alle Kanten werden zufällig erzeugt. Es muss jedoch von jedem Knoten zu jedem anderen Knoten mindestens eine mögliche Route geben. (Es ist kein formaler Beweis erforderlich, eine lückenlos nachvollziehbare Beschreibung ist ausreichend.) |
Aktuelles Thema sind ungerichtete Graphen, also sind die Kanten auch ungerichtet.
Ich habe schon versucht etwas in Python zu programmieren, aber viel weiter als Zufallsgraph der nur zufällig zusammenhängend wird bin ich noch nicht gekommen.
Habe mich auch schon über Gilbert-Graph und Erdos-Renyi-Graph informiert, aber die scheinen auch nur darauf ausgelegt zu sein, dass die Eigenschaft "Zusammenhang" zufällig entsteht oder auch nicht.
Kennt jemand einen Algorithmus oder kann mir zumindest einen Ansatzpunkt geben, wie man einen zusammenhängenden Zufallsgraphen erzeugt?
Irgendetwas nach dem Motto
1. erzeuge Zufallsgraph
2. falls nicht zusammenhängend gehe zu 1.
erscheint mir irgendwie nicht im Sinne der Aufgabenstellung.
Erst einen Zufallsgraphen erzeugen und dann nach einem festen Muster nicht verbundene Knoten einbinden erscheint mir auch nicht im Sinne der Aufgabenstellung.
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Da das Forum für den Normalsterblichen erst jetzt wieder freigegeben wurde, kann ich leider erst jetzt antworten.
1. Schritt: Nummeriere alle Knoten von 1 bis n durch.
2. Schritt: Setze für alle Knoten einen Wert mit der Bedeutung "noch nicht dabei"
3. Würfle eine beliebige Zahl als Startzahl aus, trage sie in eine Liste a ein und setze ihren Wert auf die Bedeutung "ist dabei"
4. Setze einen Zähler auf 1. (Anzahl der schon vorhandenen Knoten im Netz)
5. Würfle eine beliebige Zahl x aus a und eine beliebige andere Zahl y. Trage die Verbindung xy als Kante in eine Liste ein (z.B. Matrix).
Falls y noch nicht dabei war, erhöhe den Zähler um 1.
Setze den Wert von y auf "ist dabei".
6. Falls der Zähler <n ist, gehe wieder zu 5.
Zu 5.
Nehmen wir an, du hast bereits folgende Konstellation erwürfelt:
1 -----------3
| |
| |
| |
17 ---------29
In Liste a sind also die Zahlen 1, 3, 17 und 29.
Nun würfelst du x aus der Liste, sagen wir die 17, und eine andere Zahl y.
Ist z.B. y=29, so besteht diese Kante schon. Du kannst das überprüfen oder diese erneut eintragen. Je nach Datenstruktur überschreibst du dabei nur den bisherigen Eintrag oder du hast ihn doppelt, musst dann ggf. vor der endgültigen Ausgabe doppelten Einträge löschen (falls das so gewünscht ist).
Ist z.B. y=3, kommt eine zusätzliche Verbindung zustande, was durchaus erwünscht ist (sonst würde nur eine Kette entstehen), aber kein neuer Knoten hinzu. Deshalb bleibt der Zähler unverändert.
Ist z.B. y=49, so wird nun 17 mit 49 verbunden, 49 eingetragen als "dabei" und der Zähler um 1 erhöht. Unter den nun 5 Knoten können wieder weitere Verbindungen entstehen oder ein neuer Knoten hinzugewonnen werden.
Bemerkung: Zum Schluss entstehen sehr viele Verbindungen innerhalb des bestehenden Baumes, ohne dass ein neuer Punkt hinzukommt; der zuletzt hinzu gekommene Knoten erhält nur eine Kante, dann bricht das Verfahren ab.
Letzteres kann man abmildern, indem man nochmals eine Zufallszahl k wählt und noch k weitere Verbindungen auswürfelt.
Tatsächlich ist der Baum also nicht so ganz zufällig.
|
|
|
| |
|
Mir ist noch eine fast konträre Idee gekommen:
1. Baue zwischen den n Knoten alle [mm] \bruch{n(n-1)}{2} [/mm] Kanten auf, so dass der Graph vollständig wird (Adjazenzmatrix).
Nun schießt du erlaubte Kanten ab, indem du sie auswürfelst.
2. Würfle zunächst die Anzahl der Schüsse aus, z.B eine Zahl aus [mm] 1,2,3,...\bruch{5n(n-1)}{2} [/mm] (fünffache Kantenzahl). So oft schießt du jetzt auf Kanten.
3. Solange noch Schüsse erlaubt sind, würfle zwei Knoten aus.
a) Falls dazwischen keine Kante mehr besteht, hast du einen Fehlschuss gemacht. Der zählt aber. Gehe wieder zu 3.
b) Falls dazwischen eine Kante besteht, versuche, vom ersten zum 2. Knoten über andere Wege zu gelangen, indem du alles austestest. Falls dies gelingt, lösche die Kante; andernfalls muss sie bestehen bleiben, und du hast einen Fehlschuss getan. Gehe wieder zu 3.
4. Gib den noch bestehenden Baum aus.
|
|
|
|
