Adjazenzmatrix potenzieren = Zyklen?

[jfheins]

Hallo :-)

Mein Problem ist Graphentheoretischer Natur: Ich habe eine Adjazenzmatrix eines gerichteten Graphen. Von der Größe her wird's wohl nicht deutlich über eine 20x20 Matrix hinausgehen, aber das nur am Rande.

Meine eigentliche Frage ist: Ich habe mir ungefähr erschlossen, was es bedeutet die Matrix zu potenzieren. (Wenn vorher alle Kanten mit einer 1 und alle nicht-kanten mit einer 0 belegt sind, ist nach dem quadrieren überall eine Zahl die angibt, auf wievielen Wegen mit genau 2 Kanten man von Knoten A zu B gelangt)

Jetzt möchte ich gerne Zyklenfreiheit überprüfen. Dazu habe ich ausprobiert und festgestellt, dass bspw. eine 4x4 Matrix hoch 4 immer genau dann eine Nullmatrix ergibt, wenn der zugehörige Graph zyklenfrei ist. Und wenn er nicht zyklenfrei ist, kam stets eine Matrix heraus, die ungleich der Nullmatrix ist.
Viel interessanter als "war bis jetzt immer so" fände ich aber, wenn das immer und garantiert so ist :-)

Lange Rede, kurze Frage: Wenn man eine nxn Matrix hoch n nimmt und es kommt eine Nullmatrix heraus - kann man dann folgern dass der Graph zyklenfrei ist?

[Medium]

Ich muss zugeben bei weitem nicht mehr im Thema zu stecken, aber allein schon die Interpretation der Potenzierung müsste dies zusichern. Eine z.B. 4x4 Matrix würde ja zu einem Graphen mit 4 Knoten gehören, d.h. zyklusfrei kann ich über maximal 3 Kanten zu einer anderen gelangen. Sobald ich 4 Kanten gehen will, komme ich nirgends mehr hin, da mein Weg auf jeden Fall vorher terminiert.