Graphentheorie - ermitteln nicht isomorpher Graphen

Neue Frage »

Petra2 Auf diesen Beitrag antworten »
Graphentheorie - ermitteln nicht isomorpher Graphen
Meine Frage:
Guten Tag Com,

ich habe eine kurze Frage und zwar habe ich folgende Aufgabe zu lösen.

3a) Zeichnen Sie alle nichtisomorphen einfachen Graphen mit n=6 Knoten und m=7 Kanten.

Gut, soweit habe ich neun Stück gefunden (ohne isolierten Knoten) und frage mich nun, ob es einen leichteren Weg gibt die Anzahl zu ermitteln, als rumzuprobieren.
Vorallem, wie kann ich zeigen/beweisen, dass dies wirklich alle Möglichkeiten sind?

Sind gerade erst mit dem Thema eingestiegen, eine wirkliche Ahnung habe ich nicht unglücklich

Grüße

Meine Ideen:
Ich habe schon einiges versucht mir eine Formel aus Folgen zu erarbeiten, und dachte in Richtung Fakultät bzw. 2^(n/2) (n über 2).
Aber damit kann ich nur die isomorphen Graphen feststellen.

Habe schon ein paar Sachen über Komplementgraph gelesen aber das hatten wir noch nicht.
Petra2 Auf diesen Beitrag antworten »

Achso und bei der Aufgabe ist die Summe der Knotengrade immer 14 also 2x die Kantenlänge was ja logisch ist, da immer zwei Knoten verbunden werden.

Grüße
Abakus Auf diesen Beitrag antworten »

Hallo!

Ein einfacher Graph bedeutet, dass er keine parallelen Kanten und keine Schlingen besitzt. Zusammenhang setzt du eigenständig voraus?

Eine Idee jedenfalls ist, sich die Grade der Knoten aufzuschreiben, also etwa (3, 3, 2, 2, 2, 2) beschreibt Graphen mit 2 Knoten vom Grad 3 und 4 Knoten von Grad 2. Solche Graphen kannst du dann genauer untersuchen (leider ist es nicht so, dass 2 Graphen mit gleichen Knotengraden schon isomorph sind).

Immerhin können Graphen mit verschiedenen "Knotengrad"-Typen nicht isomorph sein.

Grüße Abakus smile
Petra2 Auf diesen Beitrag antworten »

Hi Abakus, danke für deine Antwort.
Also die Kriterien für einen einfachen Graphen sind mir bekannt.
Danke trotzdem.

In wieweit kann ich die Graphen genauer untersuchen?
Ich habe für 6 Knoten und 7 Kanten folgende Folgen:

1-1-2-2-3-5
2-2-2-2-3-3
2-2-3-3-3-3
1-1-2-2-3-3
1-2-2-2-3-4
1-2-2-2-2-5
1-1-2-2-4-4
1-1-3-3-3-3
1-2-2-3-3-3

Ich würde erstmal sagen, dass sind alle nicht-isomorphen Graphen mit diesen
Kriterien, wobei hier ja auch noch welche mit 5 verbundenen Knoten und 1 isolierten Knoten möglich währen.

Aber wie beweise ich oder kann ich erklären, dass dies alle nicht-isomorphen Graphen mit Knoten: 6 und Kanten: 7 sind?

Die Beweisprinzipien bei der Graphentheorie sind mir noch völlig unklar unglücklich
Mystic Auf diesen Beitrag antworten »

Zitat:
Original von Petra2
Die Beweisprinzipien bei der Graphentheorie sind mir noch völlig unklar unglücklich


Ja, insbesondere scheint dir nicht bekannt zu sein, dass die Summe der Knotengrade in Graphen mit einer vorgegebenen Kantenanzahl eine Konstante ist (welche?)...
Petra2 Auf diesen Beitrag antworten »

Na klar, 14 also das doppelte der Kantenzahl aber mit wieviel verschiedenen Kombination die man auch wirklich zeichnen kann funktioniert das!?
 
 
Mystic Auf diesen Beitrag antworten »

Zitat:
Original von Petra2
Na klar, 14 also das doppelte der Kantenzahl [,,,]

Du hast aber schon gesehen, dass 2 von deinen obugen 9 Möglichkeiten diese notwendige Bedingung nicht erfüllen? verwirrt

Zitat:
Original von Petra2[...]aber mit wieviel verschiedenen Kombination die man auch wirklich zeichnen kann funktioniert das!?

Glaube nicht, dass sich das so allgemein beantworten läßt... Auf jeden Fall solltest du mal wirklich alle sinnvollen Möglichkeiten hinschreiben, wo 14 Summe von 6 nichtnegativen Summanden in nichtabsteigender Reihenfolge ist... Z.B. fehlen mir da noch 1-1-2-3-3-4 und natürlich auch alle Möglickeiten, wo auch Nullen vorkommen...
Petra2 Auf diesen Beitrag antworten »

Ja die Nullen habe ich bewusst erstmal weggelassen.

Sorry bei den beiden:
2-2-3-3-3-3
1-1-2-2-3-3


ist mir das nicht aufgefallen hab mich wohl verschrieben.

Ansonsten sind die Möglichkeiten mit Nullen ja sehr beschränkt,
da ich maximal einen Knoten isolieren kann, weil bei 4 Knoten
sind sieben Kanten nicht mehr möglich, wenn wir im Bereich der
einfachen Graphen bleiben wollen.

PS: arbeite an der Liste
Petra2 Auf diesen Beitrag antworten »

Mehr als die find ich nicht:

122333
112235
112244
112334
113333
122234
222224
222233
013334
022244
022334
023333
122225
122244


Schätze aber es sind 16 nicht 14 -.-
Mystic Auf diesen Beitrag antworten »

Zitat:
Original von Petra2
Schätze aber es sind 16 nicht 14 -.-


Ist denn die Anzahl der Lösungen vorgegeben? Wenn ja, würde ich damit nicht hinterm Berg halten... Denkbar ist natürlich auch, dass es zu einer vorgegebenen Verteilung von Knotengraden mehr als nur eine Lösung gibt...

Ansonsten seh ich nach einem kurzen Überfliegen deiner Lösungen im Moment nur, dass da schon wieder eine Variante (die letzte) dabei ist, wo die Summe der Knotengrade nicht 14 beträgt... unglücklich

Edit: Zu dem, was ich oben gesagt habe: Z.B. gibt es für 2-2-2-2-3-3 die zwei Möglichkeiten eines relelmäßigen Sechsecks, das durch eine Diagionale einmal symmetrisch und einmal asymmetrisch geteilt wird...
Petra2 Auf diesen Beitrag antworten »

Ja, das ist mir schon aufgefallen, genauso, dass die Summe der letzten nicht 14 beträgt.
Eine explizite Lösung (daher Anzahl) ist leider nicht vorgegeben.

Insgesamt habe ich dann 15 gefunden, meine aber gehört zu haben, dass es sogar 24!? geben soll.
Mystic Auf diesen Beitrag antworten »

Zitat:
Original von Petra2
Insgesamt habe ich dann 15 gefunden, meine aber gehört zu haben, dass es sogar 24!? geben soll.


Ja, es sind tatsächlich 24, die zugehörigen Listen der Knotengrade sind

code:
1:
2:
3:
4:
5:
6:
7:
0  1  3  3  3  4 | 0  2  2  2  4  4 | 0  2  2  3  3  4 | 0  2  3  3  3  3 |
1  1  2  2  3  5 | 1  1  2  3  3  4 | 1  1  2  2  4  4 | 1  1  2  3  3  4 |
1  1  3  3  3  3 | 1  2  2  2  3  4 | 1  2  2  2  2  5 | 1  2  2  2  3  4 | 
1  2  2  2  4  3 | 1  2  2  3  3  3 | 1  2  2  3  3  3 | 1  2  2  3  4  2 | 
1  2  3  2  3  3 | 1  2  3  3  3  2 | 1  3  3  3  3  1 | 2  2  2  2  2  4 | 
2  2  2  2  3  3 | 2  2  2  2  3  3 | 2  2  3  2  2  3 | 2  2  2  3  2  3 |

Da mein Programm ein anderes Ordnungsprinzip hatte als die Liste der Knotengrade, erfolgt die Ausgabe dieser Listen etwas ungeordnet, aber das sollte jetzt nicht wirklich ein Problem sein... Augenzwinkern

Edit: Deine Liste von Knotengradenlisten (ohne die fehlerhafte letzte, wie schon gesagt wurde) wäre also dann tatsächlich korrekt gewesen, nur gibt es dazu eben manchmal mehrere nichtisomorphe Graphen, alllein zu 2 2 2 2 3 3 sind es vier (!)...
Petra2 Auf diesen Beitrag antworten »

Hey, danke nochmal!

Aber wie komme ich darauf?
Weil, selbst beim zeichnen der Graphen durch die Knotengrade wie 2-2-2-2-3-3
würde ich vielleicht 2 nicht-isomorphe Graphen finden, danach würde mein Kopf zerbrechen.

Gibt es da nicht irgendeine Folge o.ä. wie man auf die Anzahl kommt?
Mystic Auf diesen Beitrag antworten »

Zitat:
Original von Petra2
Gibt es da nicht irgendeine Folge o.ä. wie man auf die Anzahl kommt?


Ne, sorry, die gibt's nicht...

Aber mal ganz ehrlich, wenn du es mit all den Informationen, die du bisher gefunden bzw. erhalten hast (nämlich sämtliche Listen von Knotengraden zusammen auch mit der exakten Anzahl von nichtisomporphen Graphen zu jeder solchen Liste) trotzdem nicht schaffst, die Aufgabe zu lösen, dann solltest du einfach zugeben, dass sie dir eine Schuhnummer zu groß ist...

Ein letzter Tipp: Da die meisten Graphen zusammenhängend sind bzw. man die wenigen nichtzusammenhängenden sehr leicht finden kann, gäbe es auch noch die Möglichkeit, die 6 Bäume mit 6 Knoten durch je 2 Kanten zu einem zusammenhängenden Graphen mit 7 Kanten zu "vervollständigen"... Vielleicht fällt dir das ja leichter, insbesondere da du ja weißt, was dabei ganz am Ende rauskommen soll... Augenzwinkern
Neue Frage »
Antworten »



Verwandte Themen

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