Graph/Adjazenzliste programmieren

[Talent1704]

Hallo Zusammen,

ich sitze an einer Programmierung um alle Graphen bis zu einer bestimmten Eckenanzahl als Adjazenzliste auszugeben. Aktuell würde ich dies zunächst mit Binärvektoren, welche anschließend in eine Adjazenzliste umgerechnet werden, probieren. Oder hat hier jemand bessere Ideen/Algorithmen?
Bzw. wie kann ich das Ganze im Anschluss am besten umwandeln?

Für Ideen wäre ich dankbar.

Beste Grüße

 

[MoxxiManagarm]

alle Graphen

Alle Graphen von was?

Eckenanzahl

Was ist für dich eine Ecke in einem Graphen? Meinst du Knotenanzahl?

 

[Talent1704]

Alle möglichen Graphen bis zu einer eingegebenen Eckenzahl (Knoten)

 

[MoxxiManagarm]

Ich verstehe immer noch nicht was du mit allen möglichen Graphen meinst. Ein Graph mit 3 Knoten hat, sofern er zusammenhängend ist und ohne Berücksichtung der Kantenrichtung, bereits 4 Varianten (1-2-3 circular, 1-2-3, 1-3-2, 2-1-3), bei 4 direkt schon deutlich mehr. Ich kann mir schlecht vorstellen, dass du das für höhere n machen willst, das steigt proportional an.

 

[Talent1704]

Es geht nur um ungerichtete Graphen, die zunächst auch nicht zusammenhängend sein müssen. Heißt es sollen wirklich alle möglichen sein. Ziel ist es zu prüfen bis zu wie viel n das geht. Also ja auch für höhere

 

[MoxxiManagarm]

Ok dann hast du aber bei n=3 bereits
1-2-3 (geschlossen)
1-2-3
1-3-2
2-1-3
1-2 3
1-3 2
1 2-3
1 2 3

Oder falls die Nummerierung keinen Einfluss hat
#-#-# (geschlossen)
#-#-#
#-# #
# # #

Von einer ggf. Anzahl Knoten würde ich erst die Kanten darstellen, ob diese da sind oder nicht. Bei der nummerierten Variante für n=3 hättest du 3 Kanten 1-2, 1-3, 2-3. Die Anzahl aller möglichen Graphen sind alle möglichen Kombinationen von Sichtbar/nicht sichtbar. Eine Variante ist dann ein Vektor von true/false. Das Ergebnis basierend auf diesem boolean-Vektor kannst du sicher einfach in die Adjazenzliste umwandeln. Aber ich schätze das meintest du bereits mit deinem Ansatz.

Für die nummerierte Variante hättest du also die Vektoren entsprechend der oberen Liste und den Kanten 1-2, 1-3, 2-3 in der Reihenfolge
[true, true, true]
[true, false, true]
[false, true, true]
[true, true, false]
[true, false, false]
[false, true, false]
[false, false, true]
[false, false, false]

Setzt du es rekursiv um dann findest du sicher irgendwann die Grenze in der Rekursionstiefe. Wäre aber, vermute ich, einfacher umzusetzen. Iterativ ist es wahrscheinlich schwieriger eine Aussage zu treffen bis wohin es möglich ist.

 

[Talent1704]

Genau danke! Für n=4 wären es dann 6 Entscheidungen.
1-2, 1-3, 1-4, 2-3, 2-4, 3-4

Wie wäre das rekursiv denn aufzubauen?

 

[MoxxiManagarm]

Wie wäre das rekursiv denn aufzubauen?

Sinngemäß so:
list(n) = ('true' x list(n-1)) + ('false' x list(n-1))

 

[Talent1704]

Super danke! Das hilft mir schon

 

[MoxxiManagarm]

Ich habe vergessen zu erwähnen: In meiner Formel ist n natürlich die Anzahl der Kanten, nicht der Knoten. Du müsstest vorher von der Anzahl der Knoten auf die Anzahl der Kanten schließen.

 

[MoxxiManagarm]

Ich habs übrigens für mich auch mal getestet. Bis 7 Knoten ist es mir geglückt. Allerdings bin ich nicht am StackOverflow gescheitert (wäre bei 7 auch noch nicht relevant) sondern am OutOfMemory. Ist ja eigentlich auch klar:

7 Knoten sind 21 Kanten, also 2^21=2.1M Varianten, die im Speicher gehalten werden. Bei 8 sind es bereits 2^28=268.5M Varianten. Bei 268.5M ist mein Rechner eben gescheitert. Für mehr müsste ich irgendeinen Zwischenspeicher implementieren oder ganz anders herangehen.