Graphentheorie - ermitteln nicht isomorpher Graphen |
25.04.2010, 16:01 | Petra2 | Auf diesen Beitrag antworten » | |||||||
Graphentheorie - ermitteln nicht isomorpher Graphen 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 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. |
|||||||||
25.04.2010, 16:04 | 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 |
|||||||||
25.04.2010, 18:22 | 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 |
|||||||||
25.04.2010, 18:46 | 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 |
|||||||||
25.04.2010, 19:12 | Mystic | Auf diesen Beitrag antworten » | |||||||
Ja, insbesondere scheint dir nicht bekannt zu sein, dass die Summe der Knotengrade in Graphen mit einer vorgegebenen Kantenanzahl eine Konstante ist (welche?)... |
|||||||||
25.04.2010, 20:20 | 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!? |
|||||||||
Anzeige | |||||||||
|
|||||||||
25.04.2010, 21:12 | Mystic | Auf diesen Beitrag antworten » | |||||||
Du hast aber schon gesehen, dass 2 von deinen obugen 9 Möglichkeiten diese notwendige Bedingung nicht erfüllen?
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... |
|||||||||
25.04.2010, 21:25 | 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 |
|||||||||
25.04.2010, 22:59 | 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 -.- |
|||||||||
26.04.2010, 07:58 | Mystic | Auf diesen Beitrag antworten » | |||||||
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... 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... |
|||||||||
26.04.2010, 15:13 | 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. |
|||||||||
26.04.2010, 19:48 | Mystic | Auf diesen Beitrag antworten » | |||||||
Ja, es sind tatsächlich 24, die zugehörigen Listen der Knotengrade sind
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... 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 (!)... |
|||||||||
29.04.2010, 17:37 | 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? |
|||||||||
29.04.2010, 18:27 | Mystic | Auf diesen Beitrag antworten » | |||||||
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... |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |
|