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?