Inzidenzmatrix
Eine Inzidenzmatrix eines Graphen ist eine Matrix, welche die Beziehungen der Knoten und Kanten des Graphen speichert. Wenn der Graph Knoten und Kanten besitzt, ist seine Inzidenzmatrix eine -Matrix. Der Eintrag in der -ten Zeile und -ten Spalte gibt an, ob der -te Knoten Teil der -ten Kante ist. Steht an dieser Stelle eine 1, ist eine Inzidenzbeziehung gegeben, bei einer 0 liegt keine Inzidenz vor. Es wird davon ausgegangen, dass die Knoten von 1 bis und die Kanten von 1 bis durchnummeriert sind.
Definition
Ungerichtete Graphen
Für einen schleifenfreien ungerichteten Graphen mit
und
ist die Inzidenzmatrix
formal definiert durch:
Die Inzidenzmatrix eines ungerichteten Graphen enthält also in jeder Spalte genau 2 von 0 verschiedene Einträge.
Gerichtete Graphen
Für einen schleifenfreien gerichteten Graphen mit
und
ist die Inzidenzmatrix
definiert durch:
wobei hier einen beliebigen Knoten darstellt.
Die Inzidenzmatrix eines gerichteten Graphen enthält also in jeder Spalte genau einmal die (Startknoten) und einmal die
(Endknoten). Alternativ werden Inzidenzmatrizen manchmal auch mit umgekehrtem Vorzeichen definiert, das heißt,
, falls die Kante
am Knoten
beginnt, und
falls die Kante
am Knoten
endet. Dies ist insbesondere zu beachten, wenn man Ungleichungen betrachtet, die Inzidenzmatrizen enthalten.
Beispiele
Ungerichtete Graphen
![](http://upload.wikimedia.org/wikipedia/commons/thumb/d/d7/Inzidenzmatrix_exgraph.svg/220px-Inzidenzmatrix_exgraph.svg.png)
Wir untersuchen nun als Beispiel den rechts stehenden Graphen, der dem Haus vom Nikolaus ähnelt, mit der in dem Bild angegebenen Nummerierung der Knoten und Kanten. Um aus diesem Graphen eine Inzidenzmatrix zu erstellen, beginnen wir mit einer leeren Matrix. Diese enthält für den betrachteten Graphen Spalten und
Zeilen. Die Kanten werden in die Spalten eingetragen und die Knoten in die Zeilen.
Die Zahlen an den Kanten sind dabei nicht mit Gewichtungen der Kanten zu verwechseln. Sie beschreiben die Namen der Kanten , die in der Matrix als Spalten wiederzufinden sind.
Nun werden für jede Spalte (Kante) die dazugehörigen Knoten mit 1 markiert, alle anderen Knoten mit 0. Es ergibt sich folgende Inzidenzmatrix:
oder als Tabelle formatiert:
e1 | e2 | e3 | e4 | e5 | e6 | |
---|---|---|---|---|---|---|
v1 | 1 | 0 | 0 | 0 | 1 | 0 |
v2 | 1 | 1 | 0 | 0 | 0 | 1 |
v3 | 0 | 1 | 1 | 0 | 0 | 0 |
v4 | 0 | 0 | 1 | 1 | 0 | 0 |
v5 | 0 | 0 | 0 | 1 | 1 | 1 |
Ist die Inzidenzmatrix eines ungerichteten Graphen korrekt aufgebaut, dann muss in jeder Spalte (Kante) in Summe 2 stehen, da jede Kante exakt 2 Punkte verbindet. Ist ein Punkt mit sich selbst verbunden, steht in der entsprechenden Zelle eine 2. Die Summe jeder Zeile entspricht den Kanten, die in den dazugehörigen Punkt führen.[1]
Gerichtete Graphen
![](http://upload.wikimedia.org/wikipedia/commons/thumb/8/89/4node-digraph-embed.svg/220px-4node-digraph-embed.svg.png)
Als Beispiel einer Inzidenzmatrix eines gerichteten Graphen betrachten wir nun den rechts stehenden Graphen. Wieder nehmen wir die Nummerierung der Knoten als vorgegeben an. Die Kanten sind wie folgend nummeriert: Es ist
und
. Die Inzidenzmatrix ist also eine
-Matrix:
oder als Tabelle formatiert:
e1 | e2 | e3 | e4 | e5 | e6 | |
---|---|---|---|---|---|---|
v1 | 1 | 0 | −1 | 1 | 0 | 0 |
v2 | −1 | −1 | 0 | 0 | 1 | 0 |
v3 | 0 | 1 | 1 | 0 | 0 | −1 |
v4 | 0 | 0 | 0 | −1 | −1 | 1 |
Die Inzidenzmatrix eines gerichteten Graphen ist korrekt aufgebaut, wenn in jeder Spalte zwei Nichtnulleinträge stehen, die sich zu Null addieren.
Zusammenhang mit anderen Matrizen
Eine andere Matrix, die Graphen beschreibt, ist die Laplace-Matrix. Es ist eine -Matrix, wobei
die Anzahl der Knoten ist. Die Koeffizienten ihrer Diagonale enthalten den Grad der Knoten des Graphen, und die anderen Koeffizienten in Zeile
und in Spalte
sind gleich −1, wenn die Knoten
und
verbunden sind, und 0, wenn dies nicht der Fall ist.
Wenn die Inzidenzmatrix eines gerichteten Graphen
ist, können wir die Laplace-Matrix
durch Multiplizieren von
mit seiner transponierten Matrix
berechnen:
![](http://upload.wikimedia.org/wikipedia/commons/thumb/a/a4/Incidence_matrix_oriented.svg/150px-Incidence_matrix_oriented.svg.png)
Zum Beispiel für den gerichteten Graphen in der nebenstehenden Abbildung:
Die Adjazenzmatrix eines Graphen ist eine weitere Matrix, die den Graphen beschreibt. Es ist eine -Matrix, wobei
die Anzahl der Knoten ist. Die anderen Koeffizienten in Zeile
und in Spalte
sind gleich 1, wenn die Knoten
und
verbunden sind, und ansonsten 0. Für einen ungerichteten Graphen ist diese Matrix symmetrisch.
Die Gradmatrix eines Graphen ist eine -Diagonalmatrix, die den Grad jedes Knotens auflistet. Der Koeffizient in Zeile
und in Spalte
gibt den Grad des Knoten
an, alle anderen Koeffizienten sind 0.
Wenn die Inzidenzmatrix eines ungerichteten Graphen
ist,
seine Adjazenzmatrix und
seine Gradmatrix ist, dann gilt:
![](http://upload.wikimedia.org/wikipedia/commons/thumb/4/4c/Incidence_matrix_unoriented.svg/150px-Incidence_matrix_unoriented.svg.png)
Zum Beispiel für den ungerichteten Graphen in der nebenstehenden Abbildung:
Indem wir die Diagonale von den anderen Werten isolieren, erhalten wir:
Der Kantengraph eines ungerichteten Graphen wird erhalten, indem seine Kanten durch Knoten ersetzt werden und die neuen Knoten verbunden werden, wenn die entsprechenden ursprünglichen Kanten einen Knoten gemeinsam haben. Die nebenstehende Abbildung zeigt den Kantengraph des ungerichteten Graphen aus dem vorigen Beispiel.
Wenn die Inzidenzmatrix eines ungerichteten Graphen
und
die Einheitsmatrix ist, können wir die Adjazenzmatrix
seines Kantengraphen folgendermaßen berechnen:
![](http://upload.wikimedia.org/wikipedia/commons/thumb/1/16/Line_graph.svg/150px-Line_graph.svg.png)
Zum Beispiel für den Kantengraphen in der nebenstehenden Abbildung:
Verwendung
Speicherung von Graphen im Computer
Inzidenzmatrizen werden in der Informatik zur Speicherung von Graphen verwendet. Die Inzidenzmatrix eines Graphen mit Knoten und
Kanten benötigt einen Speicherplatz von
. Da die Platzkomplexität von Adjazenzmatrizen
beträgt, sind Inzidenzmatrizen, sollte es weniger Kanten als Knoten geben, speicherplatztechnisch effizienter.
Spektrale Graphentheorie
Des Weiteren finden Inzidenzmatrizen Anwendung in der spektralen Graphentheorie, wo versucht wird, aufgrund gewisser Eigenschaften der Inzidenzmatrix Rückschlüsse auf die Eigenschaften des repräsentierten Graphen zu ziehen.
Optimierung
Die Inzidenzmatrix eines ungerichteten bipartiten Graphen ist eine total unimodulare Matrix, genauso wie die eines Digraphen. Daher lässt sich unter gewissen Voraussetzungen die Ganzzahligkeit der Lösung eines linearen Optimierungsproblems zeigen, wenn die zulässige Menge durch eine der vorhin genannten Inzidenzmatrizen definiert wird. Insbesondere stellt dies eine Verbindung zwischen diskreter Optimierung und linearer Optimierung her.
Literatur
- Peter Knabner, Wolf Barth: Lineare Algebra. Grundlagen und Anwendungen (= Springer-Lehrbuch). Springer Spektrum, Berlin u. a. 2013, ISBN 978-3-642-32185-6.
- Reinhard Diestel: Graphentheorie. 4. Auflage. Springer, Heidelberg u. a. 2010, ISBN 978-3-642-14911-5.