Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Adjazenzmatrix - kürzester Weg mit max. 3 Kanten

Adjazenzmatrix - kürzester Weg mit max. 3 Kanten

Universität / Fachhochschule

Graphentheorie

Tags: Adjazenzmatrix, Graphentheorie, Kanten, Knoten, Matrix

anonymous

22:54 Uhr, 26.06.2019

Hallo,

ich habe folgende Aufgabenstellung:

Benutzen Sie Ihre Ergebnisse aus

A^{3}

zur Beantwortung der Frage: Zwischen welchen zwei verschiedenen Knoten bestehen die wenigsten Verbindungen aus maximal drei Kanten?

A = (\begin{array}{rcl} 0 & 2 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 & 0 & 0 \\ 1 & 1 & 2 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 & 2 & 0 & 0 \\ 2 & 0 & 1 & 0 & 1 & 0 & 2 \\ 0 & 2 & 1 & 0 & 1 & 0 & 0 \end{array})

A^{2} = (\begin{array}{rcl} 6 & 2 & 4 & 0 & 4 & 1 & 4 \\ 2 & 10 & 4 & 2 & 4 & 1 & 0 \\ 4 & 4 & 6 & 0 & 2 & 2 & 2 \\ 0 & 2 & 0 & 2 & 1 & 0 & 0 \\ 4 & 4 & 2 & 1 & 7 & 0 & 2 \\ 1 & 1 & 2 & 0 & 0 & 2 & 1 \\ 4 & 0 & 2 & 0 & 2 & 1 & 5 \end{array})

A^{3}

habe ich berechnet:

A^{3} = (\begin{array}{rcl} 12 & 28 & 16 & 5 & 17 & 4 & 4 \\ 28 & 12 & 29 & 1 & 21 & 6 & 22 \\ 16 & 29 & 12 & 4 & 22 & 2 & 8 \\ 5 & 1 & 4 & 0 & 2 & 3 & 6 \\ 17 & 21 & 22 & 2 & 12 & 8 & 9 \\ 4 & 6 & 2 & 3 & 8 & 0 & 2 \\ 4 & 22 & 8 & 6 & 9 & 2 & 0 \end{array})

Wie löse ich nun oben stehende Frage? Ich stehe momentan etwas aufm Schlauch :S

Vielen Dank vorab!

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

Hierzu passend bei OnlineMathe:

Online-Übungen (Übungsaufgaben) bei unterricht.de:

Matrizen - Determinante und inverse Matrix
Matrizen - Eigenwerte und Eigenvektoren

ermanus aktiv_icon

10:49 Uhr, 27.06.2019

Hallo,
ich kenne die Bestimmung der Anzahl Wege mit gegebener Kantenzahl
für die Adjazenzmatrizen ungerichteter Graphen ohne Mehrfachkanten.
Ich hoffe, dass diese Methode auch für gerichtete Graphen mit Mehrfachkanten
wie dem in der Aufgabe gegebenen funktioniert.
Der Eintrag in der Position

(i, j)

der Matrix

A^{n}

gibt die Anzahl
der Wege von Knoten

i

zu Knoten

j

der Länge

n

an.
Also muss man bei dieser Aufgabe die Matrix

A + A^{2} + A^{3}

bilden
und nach den Nichtdiagonalelementen mit dem kleinsten Wert suchen.
Gruß ermanus

anonymous

11:28 Uhr, 27.06.2019

Erstmal danke für dein Antwort!
Für

A + A^{2} + A^{3}

habe ich:

(\begin{array}{rcl} 18 & 32 & 20 & 6 & 21 & 5 & 8 \\ 30 & 22 & 33 & 4 & 26 & 7 & 22 \\ 20 & 33 & 20 & 4 & 24 & 5 & 10 \\ 5 & 3 & 4 & 2 & 3 & 4 & 7 \\ 22 & 26 & 24 & 3 & 21 & 8 & 11 \\ 7 & 7 & 5 & 3 & 9 & 2 & 5 \\ 8 & 24 & 11 & 6 & 12 & 3 & 5 \end{array})

Das kleinste Element, welches nicht auf der Diagonale ist, ist die 3.
Wäre dann somit eine Lösungsantwort: Knoten mit den Nummern 4 und 2
bzw. Knoten mit den Nummern 4 und 5 usw.?

ermanus aktiv_icon

11:46 Uhr, 27.06.2019

Ich würde das auch so machen (natürlich ohne Gewähr ;-)).
Gruß ermanus

anonymous

12:22 Uhr, 27.06.2019

Super, Hast mir schon sehr geholfen :-)

Nur noch zum Verständnis: Ich darf keine Elemente aus der Diagonalen nehmen, weil diese 2 Kanten besitzen, richtig?

Und: Unser Prof. meinte, wenn man entsprechend Begründet, muss man in der Matrix (für

A + A^{2} + A^{3}

) nicht alle Elemente ausrechnen. Wüsstest du wie man vorab die richtigen Knoten bestimmt ohne die komplette Matrix auszurechnen?

ermanus aktiv_icon

12:34 Uhr, 27.06.2019

zu 1.: Nein, weil die Aufgabe nach Verbindungen zwischen verschiedenen (!) Knoten fragt.
zu 2.: Ich glaube, dass man im allgemeinen wirklich alle Potenzen berechnen muss

anonymous

17:03 Uhr, 27.06.2019

Besten Dank! :-)

1474438

1474360

	Status: nicht eingeloggt	Noch nicht registriert?