[Graphentheorie] Warum kann ich diesen Graphen nicht zeichnen?

Neue Frage »

Adramelec Auf diesen Beitrag antworten »
[Graphentheorie] Warum kann ich diesen Graphen nicht zeichnen?
Hallo liebe Leute,
ich hab doch wohl noch eine Frage (sorry, dass ich das Forum so zu kleistere mit Threads..)

Folgende Aufgabe:
"Konstruieren Sie einen einfachen Graphen mit 12 Knoten, der 3 Knoten mit Grad 6, drei Knoten mit Grad 5, drei Knoten mit Grad 4 und drei Knoten mit Grad 3. Die Knoten mit Grad 6 sollen dabei mit keinem Knoten mit Grad 5 adjazent sein."

Mir ist bewusst, dass der Graphen aufgrund der Bedingung nicht zeichenbar ist, sonst wärs kein Problem (seh ich mit der Adjazenzmatrix).

Die Frage an euch wissende ist, kann ich das irgendwie "schnell checken" ob der Graph auch unter der Bedingung zeichenbar ist?

Funktioniert der Ansatz ala "ich entferne die ungerade Zahl und die Summe danach muss noch immer positiv sein". Das ist der einzige Ansatz der mir aufgefallen ist, wenn ich die 5 aus meiner Summe entferne, bleibt die Summe 13 übrig. Die ist ungerade. Mit 9 Knoten. Also auch ungerade.

Aber da habe ich einfach, so lang herumgerechnet bis was rauskommt.. Wäre halt interessant zu wissen, ob es da einen "allg. Formel" dafür gibt? :-)

Danke!
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von Adramelec
kann ich das irgendwie "schnell checken" ob der Graph auch unter der Bedingung zeichenbar ist?

Zumindest im vorliegenden Fall kann man schnell sehen, dass es unter den genannten Bedingungen nicht geht:

Von den 3er+4er Knoten gehen insgesamt Kanten aus, es gehen also auch maximal 21 Kanten zu den 5er- und 6er-Knoten.

Von den 5er+6er Knoten gehen insgesamt Kanten aus, von denen aber nur maximal Knoten "intern" (also innerhalb der 5er bzw. innerhalb der 6er) liegen können, also minimal 27 zu den 3er- und 4er-Knoten - Widerspruch!
Adramelec Auf diesen Beitrag antworten »

Super, seh ich ein.

Zuerstmal alle Kanten berechnen, die ich bilden kann mit den Knoten ohne Nebenbedingung und danach ansehen, wieviele die Knoten ich innerhalb der Knoten bilden kann mit der Bedingung (was da natürlich geht, weil ja die 6er Grad untereinander adjazent sein dürfen) und dann abziehen udn schauen ob die Summe gleich oder kleiner ist, als die möglichen.

Danke für den Tipp.
Neue Frage »
Antworten »



Verwandte Themen

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