Adjazenzmatrix

Neue Frage »

ForeRunner Auf diesen Beitrag antworten »
Adjazenzmatrix
Meine Frage:
Sei ein Graph über die Knotenmenge mit der Kantenrelation . Die Adjazenzmatrix von G ist wie folgt definiert



Zeigen Sie, dass



für alle und i,j = 1,...,n, wobei

und "Die Anzahl Pfade von i nach j der länge m"

Bermerkung: Ein Pfad der Länge n von nach ist eine Folge von Knoten in G, sodass ,
und für [

Meine Ideen:
Also was ich bis jetzt verstanden habe ist, dass G ein Tupel aus einer Knotenmenge und einer Kantenrelationsmenge, die aus einem Kreuzprodukt zweier Knoten aus der Knotenmenge besteht.

so vielmehr verstehe ich leider auch nicht. Vor allem ist mir unklar was genau die Definition von A bedeutet und was überhaupt eine Adjazenzmatrix ist.

Vielleicht komme ich ja auf einen Lösungsansatz wenn ich verstanden habe was das bedeutet.
Kann mir da jemand weiterhelfen?

Danke im Vorraus. smile
10001000Nick1 Auf diesen Beitrag antworten »

Nehmen wir z.B. den Graphen mit der Knotenmenge und .

Dieser Graph sieht so aus:
[attach]46388[/attach]

Nach Definition hat die Adjazenzmatrix an der Stelle genau dann eine 1, wenn ; d.h. wenn eine Kante von Knoten nach Knoten verläuft. Z.B. ist .

Die Adjazenzmatrix dieses Graphen ist also .

Du sollst jetzt zeigen: Wenn man die m-te Potenz der Matrix berechnet, steht an der Stelle die Anzahl der Pfade von Knoten nach Knoten , die genau Länge haben. (Die Einträge dieser m-ten Potenz von werden mit bezeichnet).

Z.B. für m=2:

D.h. es ist beispielsweise . An dem Graphen kannst du sehen, dass es genau einen Pfad der Länge 2 von Knoten 1 nach Knoten 4 gibt, nämlich .

Zeigen kannst du die Behauptung durch vollständige Induktion über .
ForeRunner Auf diesen Beitrag antworten »

Oh wow, vielen Dank dafür!

Das hat ja schon sooo viel geholfen. Ich bin gerade ein bisschen verblüfft, dass das alles so funktioniert. Mathe kann echt was schönes sein.

Jetzt wo ich das Konzept verstanden habe, ist mir auch als erstes ein Induktionsbeweis in den Sinn gekommen. Allerdings habe ich noch schwierigkeiten mir vorzustellen wie ich
von der in der Bermerkung genannten Folge auf die Dementsprechende Position in der Matrix schließen kann.

Kannst du mir da vielleicht einen Tip geben ohne mir zu viel vorweg zunehmen?
Das ist auch das erste mal, dass ich richtig mit Folgen zu tun habe, also könnte es auch an meinem mangelnden Verständnis von Folgen scheitern.
10001000Nick1 Auf diesen Beitrag antworten »

Du musst hier nichts über Folgen wissen, sondern dir im Induktionsschritt nur anschauen, wie man die Einträge der Matrix aus den Einträgen der Matrix berechnet:

Es ist , also .
ForeRunner Auf diesen Beitrag antworten »

Ah okay das verstehe ich auch. Aber wie kann ich denn davon auf schließen?

Also ich habe das mal mit der Induktion probiert. Und zwar sieht das so aus:

Wir zeigen,

und es gilt:

Induktionsanfang:

Wir beginnen mit m=2, da für m=1 direkt folgt,




für m = 2 folgt also,



(Hier bin ich mir nicht sicher wie ich argumentieren soll, dass )

Induktionsvorraussetzung:

für jedes

Induktionsschritt:

Nun setzen für für m = m+1.



(Hier wieder nicht sicher wie ich argumentieren soll, dass ist.)


Geht das überhaupt in die richtige Richtung?
10001000Nick1 Auf diesen Beitrag antworten »

Zitat:
Original von ForeRunner
Induktionsanfang:

Wir beginnen mit m=2, da für m=1 direkt folgt,


Warum machst du dann den Induktionsanfang nicht einfach für ? verwirrt
Da folgt die Behauptung doch direkt aus den Definitionen von und .

Zitat:
Original von ForeRunner


Warum sollte das letzte Gleichheitszeichen gelten?

Du brauchst für den Schritt nur . (Oder das, was ich in meinem letzten Beitrag geschrieben habe, wenn du den Induktionsschritt zeigen willst.)

Gucken wir uns für festes mal den Summanden an. Was ist nach Induktionsvoraussetzung? Und was könnte dann dieses Produkt mit sein? (Mach am besten eine Fallunterscheidung oder .)
 
 
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »