Aufgabe 8.3

[fake]

iwi weiß ich nicht genau wie ich hier vorgehen soll, kann mir jemand nur n ansatz sagen wie man das prüfen kann?

[ryo]

Als allererstes schaust du, ob auf der Diagonalen überall 1er sind (reflexive Hülle) -> jeder knoten hat pfad zu sich selbst
Ansonsten würde ich einfach mal versuchen, aus der Wegematrix auf einen möglichen Graphen zu kommen, und dann sollte irgendwo ein widerspruch auftreten.

die Lösungen (ohne zeichnungen):

PRIME_BBCODE_SPOILER_SHOW PRIME_BBCODE_SPOILER: auf Anzeigen klicken

M1 nein, bei Umformen in Graph tritt widerspruch auf, z.b. laut M2: von 4 kommt man zur 1, von der 1 zur 2, also logischerweise auch von der 4 zur 2, aber Matrix nach gibt es keinen Weg von der 4 zur 2

M2 nein, in Diagonale an einer stelle keine 1

M3 ja
M4 ja

[fake]

so geht das also, alles klar danke

[markusj]

Ich bin mir nicht sicher, ob die sich alle auf den selben Graphen beziehen ... ich muss am Donnerstag nochmal den Tutor fragen.

mfG
Markus

[Daniel B.]

Die Aufgaben können sich garnicht auf den gleichen Graphen beziehen, es ist ja verlangt : Geben Sie für Matrizen Mi, die Wegematrizen sein können, einen Graphen an

da es mehrere sind müsste man mehrfach den gleichen graphen zeichnen... macht irgendwo keinen sinn

[Cauchy]

@ ryo @ M2:

Schau dir mal bitte folgende Adjazenzmatrix an und sag mir wie ich von dort nicht auf komme.

PRIME_BBCODE_SPOILER_SHOW PRIME_BBCODE_SPOILER: auf Anzeigen klicken

Wenn man diese nämlich durchmultipliziert kommt man auf

[ryo]

Unser Tutor hat uns erklärt, dass in der Diagonale überall ne 1 stehen muss.
Grund denke ich: Jeder Knoten hat einen Pfad der Länge 0 zu sich selbst.
Aber ACHTUNG: Du hast geschrieben "Adjazenzmatric". Das hier sind keine Adjazenzmatrizen (also, welcher Knoten mit welchem verbunden ist) sondern Wegematrizen, also von welchem Punkt es einen Weg beliebiger Länge zu einem anderen Punkt gibt.

Ach ja,

Ich bin mir nicht sicher, ob die sich alle auf den selben Graphen beziehen ... ich muss am Donnerstag nochmal den Tutor fragen.

mfG
Markus

Nein, sind definitiv jeweils unterschiedliche Matrizen / Graphen. Kommt auch was ganz unterschiedliches raus.

Eine kleine Frage hätte ich da selbst noch: Da die 1 in der Diagonale ja eigentl. auch für Pfad Länge 0 stehen kann, muss man im Graph dann strenggenommen doch im Prinzip keine Schlingen zeichnen. Oder sehe ich das falsch? Naja, ich hab sie auf jeden Fall mal hingezeichnet, falsch ists ja nicht, und ob man jetzt zwei Kringel mehr macht...

[deepmessage]

@ryo: Eine Schleife ist ein Pfad der Länge 1.

[ryo]

@ryo: Eine Schleife ist ein Pfad der Länge 1.

äh ja. hab ich irgendwo was anderes gesagt? Dann ab ich mich missverständlich ausgedrückt. sry

Weiß jetzt nicht, was du meinst. Meinst du die Erklärung, warum überall eine 1 bei jeder Art von Wegematrix, da Weg zu sich selbst? Ist doch logisch, ich geh halt garnicht weg...

Oder meinst du das am Schluss, ob nun Schlingen zeichnen?
Ich habe nur überlegt, ob es jetzt besser ist, die Schlingen wegzulassen oder nicht. Natürlich gibt es mehrere Lösungen für eine Wegematrix. Ist halt die Frage, welche jetzt "am schönsten" wäre.

[Dre]

PRIME_BBCODE_SPOILER_SHOW PRIME_BBCODE_SPOILER: auf Anzeigen klicken

M1 nein, bei Umformen in Graph tritt widerspruch auf, z.b. laut M2: von 4 kommt man zur 1, von der 1 zur 2, also logischerweise auch von der 4 zur 2, aber Matrix nach gibt es keinen Weg von der 4 zur 2

M2 nein, in Diagonale an einer stelle keine 1

M3 ja
M4 ja

Hab ich genauso. Mich würds' nur mal interessieren ob man bei 8.2 genauso vorgeht wie bei der analogen
Aufgabe der 7... da die Lösungen des letzten Blattes schon ewig ausstehn'. Hab halt wieder zeilenweise mit
Text erklärt wie sowas auszusehen hat.