Inzidenzmatrix
-
Hallo Mathe-Gurus,
meine Frage dreht sich um das Thema Inzidenzmatrix. Mir ist nämlich nicht ganz klar wie ich aus einer gegebenen Matrix den Graphen konstruieren soll. Mein Problem sind da irgendwie die Kanten. Ich weiß zwar wie der Eingangs- bzw. Ausgangsgrad eines einzelnen Knoten ist, aber ich weiß nicht welche Kanten welche Knoten verbinden.
Das kann doch nicht so schwer sein
Schon mal danke
Gruß
Marcus
-
Wenn in Zeile i, Spalte j eine 1 steht, dann gibt's ne Kante von Knoten i zu Knoten j. Noch Fragen?
Jester
-
Ja, Jester.
Das was du beschrieben hast ist doch eine Adjazenzmatrix, wenn ich mich nicht irre. Bei der Inzidenzmatrix sind in Zeile i die Knoten und in Spalte j die Kanten beschrieben.
Bsp.
| 1 0 0 0 |
|-1 1 -1 0 |
| 0 -1 1 0 |
| 0 0 0 -1 |Wie sieht der Graph aus?
-
Ahso, ja entschuldige.
Schau Dir die Spalten an. Jede Spalte steht für eine Kante.
Dort wo die Einträge stehen sind Anfang bzw. Ende der Kante. Beachte: Es gibt nur zwei Einträge ungleich 0 pro Spalte.
Was +1/-1 bedeutet kann ich Dir leider nicht sagen, ist wohl auch Definitionssache. Eine heißt wohl Kante beginnt hier, Kante endet hier.Die einzelne Zahl ist vermutlich eine Schlinge (Kante zu sich selbst).
MfG Jester
-
Hmm, also -1 bedeutet, Kante j kommt in Knoten i an und 1, Kante j geht von Knoten i aus.
Gut dann weiß ich welche Kanten von welchen Knoten ankommen bzw. abgehen. Aber wo gehen denn die einzelnen Kanten hin.
Ich seh den Wald vor lauter Bäumen nicht mehr, glaub ich
-
Soweit ich das durch die Postings vorher verstanden habe:
(Annahme: 1 = Kantenstart, -1 = Kantenende)
Jeder Zeile wird ein Knoten zugeordent, ich nenne sie 1 für die erste Zeile etc.
Für die Matrix oben:
Kante von 1 zu 2
Kante von 2 zu 3
Kante von 3 zu 2
Schlinge an Knoten 4Andere Frage: Wofür sind solche Graphen bzw. ihre Matrizen da?
Ich hab bis jetzt nur mathematische Spielereichen gesehen, die wir damit gemacht
habe. Was kann man damit in der (informatischen) Praxis tun?
-
Du kannst damit halt bestimmte Operationen sehr einfach beschreiben. Zum Beispiel Kanten rumdrehen durch Multiplikation mit -1.
Und wenn Du die Zuordnung rumdrehen willst: Knoten zu Kanten statt Kanten zu Knoten mußt Du nur transponieren.
Allgemein kann man damit Relationen über endlichen Mengen mit Hilfe von Matrizen beschreiben und damit einige Operationen sehr komfortabel ausdrücken, bzw. überhaupt erst richtig behandeln.MfG Jester
-
taurin
******ein praktisches beispiel ist zb. das finden des kürzesten weges innerhalb dieses graphen wobei der graph ein straßennetz oder was auch immer symbolisiert...und für manche der algorithmen eignen sich halt mal indizenzmatrizen anstatt adjazenzmatrizen besser oder für schwach besetzte graphen zb. adjazenzlisten
bye
tt
-
Ah, jetzt ist es klar. War irgendwie auf der Leitung gesessen ;-).
Danke Leute!
Gruß
Marcus
-
Dankschön. Dann hat das doch alles einen Sinn, was ich lerne
