Graphentheorie

Hallo,

Aufgabe a,b,c sind klar. Nur d nicht. Die Regel gilt doch nach wie vor nur das ich auf keine Nullmatrix komme, da es einen Zyklus gibt ?!?

Auf dem Link ist ein Screenshot der Aufgabenstellung.

Graphenaufgabe

Ich wäre um jede Hilfe dankbar...

graphi schrieb:

Hallo,

Aufgabe a,b,c sind klar. Nur d nicht. Die Regel gilt doch nach wie vor nur das ich auf keine Nullmatrix komme, da es einen Zyklus gibt ?!?

Auf dem Link ist ein Screenshot der Aufgabenstellung.

Graphenaufgabe

Ich wäre um jede Hilfe dankbar...

Bzw. bei c steht ja auch schon das ich die Regel abändern muss und bei d für welche Graphen diese Regel gilt??

Ich denke doch für alle gerichteten Graphen?!?

CStoll

Was hast du denn zu c herausbekommen? Vielleicht hilft dir das (und die Begründung, warum für den veränderten Graphen die Regel aus (a) nicht mehr gilt) weiter).

(Noch ein Bonustipp: der neue Graph ist immer noch gerichtet, aber er hat etwas, was der ursprüngliche Graph nicht hatte ;))

Jester

Nein, die Regel kann ja nicht für alle gerichteten Graphen gelten, weil sie in c) nicht gilt. Meine Vermutung wären azyklische Graphen. Aber sicher bin ich nicht.

Schreib Dir doch mal auf, wie Element a_ij von A^k aussieht (abhängig von A^(k-1)). Außerdem würde ich mir diese A^k mal mit irgendeinem programm ausrechnen und mal anschaun. Da lässt sich dann sicher was mit anfangen.

Also, vielen Dank euch ersteinmal.

Ich habe die Adjazensmatrizen des erweiterten Graphen bis A^8 ausgerechnet. Also die Adjazensmatrix mit sich multipliziert. Sie stimmen auch, bzw. leifern genau die Anzahl der Wege der Länge n. Was mir aufgefallen ist das Matrizen mit geradem Exponent und die mit ungeradem Exponent jeweils gleich sind. Das lässt sich durch den Zyklus erklären. Aber hier mal die Matrizen.

Elemente der n. Potenz A^n der Adjazensmatrix

Und warum die Regel aus a nicht stimmen soll weiß ich immer noch nicht?

Jester

Kannst Du denn umgekehrt erklären, warum die Regel aus a) für den Ausgangsgraphen stimmt?

JA kann ich. Ich mache das mal so
1 nenne ich A
2 nenne ich B
3 nenne ich C
4 nenne ich D

Ich nehme mir mal bei der A^2 Matrix den die Verbindung von AD (von A nach D) raus (also AD^2).
AA z.B. heißt von Knoten A nach Knoten A

Hier noch einmal die Adjazensmatrix:
A B C D
A 0 1 1 1
B 0 0 0 1
C 0 1 0 1
D 0 0 0 0

Bei der Matrixmultiplikation mach ich ja für die Kante AD folgendes:

AD^2=AA*AD+AB*BD+AC*CD+AD*DD
Ich gehe also alle Möglichkeiten der Länge 2 von A nach D durch. Ist eine Verbindung nicht vorhanden so ist diese in der Adjazensmatrix und der Multiplikation Null. Also um von A nach D zu kommen der Länge 2 wäre eine Möglichkeit von A nach A (Schleife) und dann von A nach D. Da keine Schleife existiert ist das 0

Bei AD^3 mache ich dann folgendes:
AD^3=AA2*AD+AB^2*BD+AC2*CD+AD^2*DD

Da alle Möglichkeiten der jeweiligen Länge durchgegegangen werden stimmt die Regel.

Aber ich finde irgendwei immer noch nicht raus warum sie für den erweiterten Graphen (mit Zyklus) nicht gilt.

Nur um das ganze abzurunden. Man spricht wenn ein Knoten mehrfach durchlaufen wird nicht mehr von einem Weg (habe mir die Definition des Weges nicht mehr angeguckt) sondern von einem Kantenzug. Deshalb gilt die Regel aus 1 nicht.

Und für d: Für alle azyklisschen gerichteten Graphen (wie von Jester vermutet).