Inzidenzmatrix

11.12.2017, 18:40	FelNa1109	Auf diesen Beitrag antworten »
Inzidenzmatrix Ich habe ein Problem bei dieser Aufgabe: "Es sei $\begin{eqnarray} G=(V,E) \end{eqnarray}$ ein (nicht notwendig zusammenhängender) Graph und es bezeichne $\begin{eqnarray} B^{V\times E} \end{eqnarray}$ seine Knoten-Kanten Inzidenzmatrix. Zeigen Sie: $\begin{eqnarray} rang B = \|V\| - k \end{eqnarray}$ wobei k die Anzahl der bipartiten Zusammenhangskomponenten von G bezeichnet. Wäre net wenn mir jemand Denkanstöße geben könnte, Danke.
11.12.2017, 19:41	sibelius84	Auf diesen Beitrag antworten »
Hallo FelNa1109, hast du das denn verstanden mit den "bipartiten Zusammenhangskomponenten"? Du brauchst im Prinzip die folgenden Zutaten: (1) Sei G=(V,E) ein zusammenhängender Graph und B seine Inzidenzmatrix. Dann ist Rang B = \|V\|, falls G nicht bipartit ist, und Rang B = \|V\|-1 sonst. (War evtl. in der Vorlesung? Sonst müsste man das selber zeigen.) (2) Sei G=(V,E) ein Graph mit den Zusammenhangskomponenten G_j=(V_j,E_j), j=1,...,r, mit Inzidenzmatrizen B bzw. B_1, ..., B_r. Dann lässt sich B = diag(B_1, ..., B_r) schreiben (Blockdiagonalmatrix), so dass $\begin{eqnarray} rk(B) = \sum_{i=1}^r rk(B_i) \end{eqnarray}$ . Jedes einzelne für sich ist evtl. leichter zu zeigen als die Behauptung als ganzes? LG sibelius84
11.12.2017, 20:07	FelNa1109	Auf diesen Beitrag antworten »
Hallo, erstmal danke fürs antworten. Ich habe gerade die Vorlesung durchgeschaut, und wir haben davon noch nichts bewiesen. Wie müsste ich denn am besten vorgehen um 1) und 2) zu zeigen? Das Ziel ist ja denke ich, dass wenn ich die rk B_i Inzidenzmatrizen aufsummiere entweder \| V_i \| oder \| V_i \|-1 als Summanden habe. Die gesamte Summe wäre dann \| V \|-k wobei k eben die Anzahl meiner Zusammenhangskomponenten ist.
11.12.2017, 20:39	sibelius84	Auf diesen Beitrag antworten »
Zu (1): Wenn du einen zusammenhängenden Graphen hast, dann sind auf jeden Fall alle n Knoten mit irgendeiner Kante verbunden. Du kannst also die ersten n-1 Spalten der Inzidenzmatrix so befüllen, dass oBdA die erste Spalte gerade e_1+e_2 ist, und dann immer eine Zeile tiefer noch mal eine 1 reinkommt. So kriegst du schnell, dass Rang B >= n-1 für jeden zusammenhängenden Graphen G. Wenn nun der Graph bipartit ist, so gibt es eine Partition $\begin{eqnarray} V=U\stackrel{\cdot}\cup W \end{eqnarray}$ , so dass alle Kanten nur zwischen U und W verlaufen (und keine Kanten innerhalb von U oder W). Wir schreiben die Inzidenzmatrix noch mal (gedanklich / mit Pünktchen, Sternchen) auf, jetzt aber mit den umsortierten Knoten für die Zeilen, also die ersten s Zeilen für U, die Zeilen ab s+1 bis r für W. Da tragen wir (wieder gedanklich) alles von oben noch mal ein, und benutzen die Tatsache von oben, dass bereits die ersten n-1 Spalten den vollen Rang n-1 haben (folgt aus Gauß bzw. Elementaren Zeilenumformungen, wir haben ja nur vertauscht). Nun muss man sich überlegen, dass wegen der Bipartitheit jeder Inzidenzvektor e_i+e_j mit i <=s, j > s, den man noch dazutun könnte, von den restlichen bereits linear abhängig ist. Alle Vektoren y € im B erfüllen die (Hyper-)Ebenengleichung $\begin{eqnarray} y_1+\ldots + y_s - y_{s+1}-\ldots-y_r = 0 \end{eqnarray}$ , also kann im B höchstens (n-1)-dimensional sein. Wenn der Graph nicht bipartit ist, so macht man trotzdem irgendeine Partition in U und W und schreibt sich dann (gedanklich / Pünktchen / ...) die Inzidenzmatrix noch mal auf. Wieder folgt aus dem eben Bewiesenen, dass die ersten n-1 Spalten linear unabhängig sind. Da ja der Graph nicht bipartit ist, muss es nun noch eine Spalte der Matrix geben, die die Form e_i+e_j hat mit i,j<=s oder i,j>s. Diese Spalte kann sich aus den restlichen nicht linearkombinieren lassen, denn jede nichttriviale Linearkombination der restlichen Spalten würde sowohl in die Zeilen mit Indices <= s als auch in diejenigen mit Indices > s etwas hineinschreiben, was man nicht durch die anderen Vektoren wieder eliminieren könnte. Vielleicht soweit erstmal, Punkt (2) ist eigentlich auch relativ einfach zu sehen, wenn man sich das mal sauber aufschreibt und durchspielt.
11.12.2017, 21:47	FelNa1109	Auf diesen Beitrag antworten »
Habe ich einen Graph G=(V,E) mit Zusammenhangskomponenten G_j=(V_j,E_j), j=1,...,r, mit Inzidenzmatrizen B bzw. B_1, ..., B_r. Dann ist ja die Inzidenzmatrix definiert wie folgt: $\begin{eqnarray} b_{i,j} = 1 \end{eqnarray}$ , falls $\begin{eqnarray} i \in j \end{eqnarray}$ $\begin{eqnarray} b_{i,j} = 0 \end{eqnarray}$ , sonst Wobei $\begin{eqnarray} i \end{eqnarray}$ die Knoten und $\begin{eqnarray} j \end{eqnarray}$ die Kanten von G sind. Da G jetzt in Zusammenhangkomponenten (kurz: ZSHK´n) unterteilt ist, kann ein Knoten $\begin{eqnarray} i_{k} \in V_i \end{eqnarray}$ auch nur mit einer Kante $\begin{eqnarray} j_{k} \in E_i \end{eqnarray}$ verbunden sein. Deswegen sind die Zeilen welche die Knoten $\begin{eqnarray} i_{l} \notin V_i \end{eqnarray}$ bezüglich der Spalten $\begin{eqnarray} j_{k} \in E_i \end{eqnarray}$ und die Spalten $\begin{eqnarray} j_{l} \notin E_i \end{eqnarray}$ bzgl. der Zeilen $\begin{eqnarray} i_{k} \in V_i \end{eqnarray}$ , aufgefüllt nur mit Nullen. Da das für jede ZSHK gilt, enstehen Blöcke, sodass B = diag(B_1, ... , B_r) Da die Zeilen und Spalten offenbar lin. unabhängig sind, addieren sich die Ränge und es gilt: $\begin{eqnarray} rk(B) = \sum\limits_{i=1}^{r} rk(B_i) \end{eqnarray}$
11.12.2017, 22:38	sibelius84	Auf diesen Beitrag antworten »
Ok, klingt ganz gut. Der Kernpunkt für die Darstellbarkeit der 'großen' Inzidenzmatrix als Blockdiagonalmatrix aus den 'kleinen' Inzidenzmatrizen ist einfach: Knoten aus G_i können nicht mit Kanten aus G_j inzidieren, wenn i ungleich j. "Offenbar linear unabhängig" würde ich im letzten Teil nicht schreiben; bei Blockdiagonalmatrizen addieren sich immer die Ränge (betrachte zur Verdeutlichung das Beispiel einer Diagonalmatrix, mit lauter '1x1-Matrizen' auf der Diagonale), das wird man aus LA voraussetzen dürfen, hoffe ich.
Anzeige

11.12.2017, 22:46	FelNa1109	Auf diesen Beitrag antworten »
Ok. Dann muss ich jetzt ja nur noch die Summe für die B_i ausrechenen, wobei deren Rang nach 1) entweder \| V_i \| oder eben \| V_i \|-1 ist. Sind dann eben k ZSHK´n bipartit ist die gesamte Summe \| V \| - k. Hast mir mal wiedeer sehr geholfen, Dankeschön.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »