X-No-Archive: Yes
Post by Andreas HansenIch hätte noch eine zweite Frage: Wenn nun aber der Graph vollständig
verbunden ist, wieso sind dann geeignete Teilmengen von Zeilen der
Matrix linear unabgängig, aber wieso sind "alle" Zeilen von B linear
abhängig?
Das stimmt bei ungerichteten Graphen nicht,
(1 0 1)
(1 1 0)
(0 1 1)
hat linear unabhängige Zeilen, und das ist für alle n>2 so.
Bei gerichteten Graphen dagegen ist
a) klar, daß die Zeilen linear abhängig sind, weil die Summe aller
Zeilen immer 0 ergibt (in jeder Spalte stehen eine 1 und eine -1).
b) klar, daß 'geeignete' Teilmengen der Zeilen linear unabhängig sind
(solche geeigneten Teilmengen enthält jede Menge von Vektoren)
Interessant ist aber Folgendes (darauf wolltest Du vielleicht hinaus):
Ist D ein gerichteter Graph mit n Knoten, der einfach zusammenhängend
ist, dann sind beliebige (n-1) Zeilen der Inzidenzmatrix linear unabhängig.
Warum ist das so? Den Beweis lasse ich Dir erstmal selbst, ich gebe Dir
aber ein paar 'Wegpunkte':
* Spalten einer Inzidenzmatrix, deren Kanten keine Zyklen (ungerichtet)
bilden, sind linear unabhängig.
* Einfach zusammenhängende Graphen enthalten einen (ungerichteten)
Spannbaum mit (n-1) Kanten. Andere Kanten sind für den Spaltenrang
unerheblich.
* Die Inzidenzmatrix eines Spannbaumes hat den Rang (n-1).
* Beim Schritt, warum man eine beliebige Zeile streichen darf, hilft die
Überlegung, wie man im Rest die Determinante entwickelt.
Gruß & HTH
Bastian