Graphentheorie - Anzahl möglicher Verbindungen von Knoten

Neue Frage »

adnake Auf diesen Beitrag antworten »
Graphentheorie - Anzahl möglicher Verbindungen von Knoten
Meine Frage:
Guten Tag,

ich beschäftige mich derzeit im Rahmen meiner Bachelorarbeit mit einem Graphenproblem und würde mich über jegliche Anregung freuen.

Angenommen, es gibt n Knoten und m "Super-Knoten". Jeder dieser n Knoten muss mit einem dieser m "Super-Knoten" verbunden sein, die "Super-Knoten" müssen jedoch nicht untereinander verbunden sein und können auch freistehend sein, wenn alle n Knoten mit einem der anderen "Super-Knoten" verbunden sind.

Wie viele einzigartige Möglichkeiten gibt es, einen gültigen Graphen zu erstellen?

Meine Ideen:
Bei n Knoten gibt es laut TSP (n-1)!/2 Möglichkeiten, wenn jeder Knoten in einem Graphendurchlauf nur einmal besucht wird. Dementsprechend würde eine weitere Verbindung zu einem der m Knoten zu einem gültigen Graphen führen und die Anzahl der Möglichkeiten würde (n-1)!/2+1 lauten.

Was jedoch, wenn ich die Rahmenbedingung, dass jeder Knoten nur einmal besucht wird, aufhebe und spinnennetzartige Graphen zugelassen werden?
adnake Auf diesen Beitrag antworten »

Noch einmal zu meinen Überlegungen: die Anzahl der Möglichkeiten würden in meinem Beispiel natürlich ganz simpel lauten.
 
 
HAL 9000 Auf diesen Beitrag antworten »

Hmm, ich verstehe das jetzt so:

Einzige Bedingung ist, dass jeder der Knoten mit mindestens einem der Superknoten verbunden ist. D.h., ansonsten ist alles zugelassen, bis hin zum vollständigen Graphen der Knoten ?

Dann ist die Anzahl möglicher Graphen gleich .
adnake Auf diesen Beitrag antworten »

Richtig, das ist die einzige Bedingung. Jedlicher Graph ist zugelassen, auch der vollständige Graph und auch ein Graph, in welchem einige der Knoten mit keinem anderen Knoten verbunden sind (solange alle Knoten mit mindestens einem der Knoten verbunden sind). Es muss auch kein zusammenhängender Graph sein.

Ich habe gemerkt, das ich und sowohl als Index als auch als Nummer gebraucht habe, aber ich hoffe die Problemstellung kam dennoch rüber.

Zitat:
Dann ist die Anzahl möglicher Graphen gleich [...]

Ich habe das Ganze mal für m=1, n=2 und m=2, n=2 getestet. Leider wird die Größe durch diese Formel unterschätzt (für das erste Paar kommt 2 raus, richtig ist 3. Für das zweite paar kommt 36 raus, richtig ist 48 oder mehr).

Ich habe für die beiden Beispiel mal meine Skizzen dazu angehängt. Eventuell habe ich für m=2 und n=2 nicht einmal alle Möglichkeiten gefunden.
adnake Auf diesen Beitrag antworten »

EDIT: Für m=1 und n=2 habe ich eine Konfiguration vergessen, in der alle Kanten sind. Also macht das vier Möglichkeiten statt drei.
adnake Auf diesen Beitrag antworten »

Neue Erkenntnis: für m=1 gilt die Integer-Sequenz A001187 mit n+1 Knoten.

Ist es möglich, eine Sequenz/Formel für meine Problemstellung mit m ungleich 1 zu finden? Hierdurch erweitert sich der Lösungsraum ja noch einmal erheblich.
HAL 9000 Auf diesen Beitrag antworten »

bedeutet, dass die beiden einfachen Knoten mit dem einen Superknoten verbunden sein müssen. Es verbleiben also nur zwei Möglichkeiten: Mit oder ohne Verbindungskante der beiden einfachen Knoten. Bei deinen drei skizzierten Varianten erfüllen die beiden letzten Skizzen nicht die Bedingung, dass die beiden einfachen Knoten direkt mit einem Superknoten verbunden sind. Dafür fehlt aber eine, nämlich der vollständige Graph. unglücklich

Kann natürlich sein, dass ich "verbunden" anders gedeutet habe als du: Nämlich als direkt verbunden durch eine Kante - während du es womöglich so auffasst, dass nur ein Weg zwischen beiden existieren muss. verwirrt

Letzteres ist natürlich viel ekliger, da passe ich.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »