Aufgabe 8.3

[ryo]

meinst du die a) oder b) ?

bei der a) hab ich massig text (der arme Tutor XD)

bei der b) hab ich en bissl was mit Pünktchen gemacht, hätten wir letztes mal auch so machen sollen

PRIME_BBCODE_SPOILER_SHOW PRIME_BBCODE_SPOILER: auf Anzeigen klicken

(1) -> (2) -> (3) -> ...-> (n-1) -> (n) -> (1)

die 1 am schluss ist natürlich die 1 vom Anfang, wollte hier aber nicht probieren, großartig was "im kreis" zu basteln, da es das wohl von der formatierung her vllt verhauen würde

[Dre]

...ja genau, die Skizze hab ich auch. Aber ich dachte halt immer, dass das ohne Erklärung nich' ausreicht, deswegen hab ich noch ne halbe Seite Text dazu.

[ryo]

Unser Tut hat letztes Mal gemeint, einfach ein paar Pünktchen einzeichnen würde reichen.
Wobei das ja gerade das letzte mal en bissl blöd war. Da weiß ich nicht, ob die Zeichnung wirklich 100% aussagekräftig war, da wird ne Erläuterung nicht ganz schlecht wegesen sein.
Aber dieses mal... das Dingens da ist doch jetzt nicht soo kompliziert^^ Vor allem haben wir in der Klausur keine Zeit, ne halbe Seite zu so nem Graphen zu schreiben.

[Cauchy]

Also, hier meine Überlegung:

Meine Adjazenzmatrix meines Graphen sieht wie folgt aus:




Jetzt multipliziert man die Matrix mit sich selbst, also quadriert man die Matrix, und erhält alle Wege der Länge zwei.
Hier meine Rechnung:




So und jetzt noch die sgn-Funktion mit einbeziehen:



Also existiert eine solcher Graph.
q.e.d.

PS: Ich, als Cauchy, würd mich nicht immer auf Tutoren verlassen, die labern manchmal zu viel

[Dennis]

Wenn ich das richtig verstanden habe muss man um auf die Wegematrix zu kommen das doch zuerst mit der Einheitsmatrix addieren, wodurch dann logischerweise in der Diagonalen überall 1 steht, weil man von jedem Knoten eben mit dem Pfad der Länge 0 zu sich selbst kommt.

[|silent]

Was muss denn eine Wegematrix alles erfüllen, dass sie eine Wegematrix eines Graphen ist?

[ryo]

Cauchy, ich weiß nicht genau, worauf du hinauswillst. Hast du die Aufgabenstellung falsch gelesen??

Es heißt

Welche der folgenden Matrizen können Wegematrizen eines Graphen sein?

AAAh, nein, jetzt verstehe ich, du willst zeigen, dass du auf diese Matrix kommst, indem du von ner Adjazenzmatrix ausgehend (die genau so aussieht wie die Wegematrix) auf die Wegematrix selbst kommst.

Nun ist dein einziger Fehler der: Um die Wegematrix zu erhalten, musst du die Adjazenzmatrix mit der Einheitsmatrix verbinden, also auf gut Deutsch noch die Diagonale ausfüllen. Siehe z.B. Script S. 91 F1 = E0 + E1.
Ein Knoten hat immer einen Weg der Länge 0 zu sich selbst!!

Hoffe mal, jetzt ist alles klar.

[Cauchy]

Vielen Dank für die einleuchtenden Worte, macht auch irgendwie Sinn
Demnach zieht auch die Begründung mit der Diagonalen!

[patrick]

das mit den 1en auf der Diagonalen geht auch ganz schnell aus der Definition der Wegematrix hervor:
1 falls (i, j) ∈ E*
0 sonst

(in E* ist auch E^0 enthalten, und man kommt in 0 Schritten von v zu v, also ist die Matrix zu E^0 gleich der Einheitsmatrix)

[markusj]

Was muss denn eine Wegematrix alles erfüllen, dass sie eine Wegematrix eines Graphen ist?

1. Jeder Knoten muss eine Schlaufe haben ( <=> Hauptdiagonale mit Einsen besetzt).
2. Jeden Knoten B, den du von Knoten A über Umwege erreichen kannst, muss auch eine direkte Verbindung A->B haben.

Die Wegematrix gibt im Endeffekt alle möglichen Wege von A nach B wieder - gibt es im Graphen (Um-)Wege, die in der Wegematrix nicht abgedeckt werden, ist es keine Wegematrix (was fürn Satz ...)

mfG
Markus