imported>Alexander Nikolaj Block: /* growthexperiments-addlink-summary-summary:1|1|0 */

2025-04-08T20:28:22Z

growthexperiments-addlink-summary-summary:1|1|0

Neue Seite

{{Dieser Artikel|behandelt die ''Inzidenzmatrix'' von [[Graph (Graphentheorie)|Graphen]]. Eine allgemeinere Sichtweise wird im Artikel zu [[Inzidenzstruktur#Inzidenzmatrix|Inzidenzstruktur]]en beschrieben.}}

Eine '''Inzidenzmatrix''' eines [[Graph (Graphentheorie)|Graphen]] ist eine [[Matrix (Mathematik)|Matrix]], welche die Beziehungen der [[Knoten (Graphentheorie)|Knoten]] und [[Kante (Graphentheorie)|Kanten]] des Graphen speichert. Wenn der Graph <math>n</math> Knoten und <math>m</math> Kanten besitzt, ist seine Inzidenzmatrix eine <math>n \times m</math>-Matrix. Der Eintrag in der <math>i</math>-ten Zeile und <math>j</math>-ten Spalte gibt an, ob der <math>i</math>-te Knoten Teil der <math>j</math>-ten Kante ist. Steht an dieser Stelle eine 1, ist eine [[Inzidenzstruktur#Inzidenzmatrix|Inzidenzbeziehung]] gegeben, bei einer 0 liegt keine Inzidenz vor. Es wird davon ausgegangen, dass die Knoten von 1 bis <math>n</math> und die Kanten von 1 bis <math>m</math> durchnummeriert sind.

== Definition ==

=== Ungerichtete Graphen ===

Für einen schleifenfreien [[Ungerichteter Graph|ungerichteten Graphen]] <math>G = (V, E)</math> mit <math>V = \{ v_1, \dotsc, v_n \}</math> und <math>E = \{ e_1, \dotsc, e_m \}</math> ist die Inzidenzmatrix <math>B = (b_{i, j})</math> formal definiert durch:
:<math>
b_{ij} := \begin{cases}
1, & \text{ falls } v_i \in e_j \\
0, & \text{ sonst}
\end{cases}
</math>

Die Inzidenzmatrix eines ungerichteten Graphen enthält also in jeder Spalte genau 2 von 0 verschiedene Einträge.

=== Gerichtete Graphen ===

Für einen schleifenfreien [[Gerichteter Graph|gerichteten Graphen]] <math>G = (V, E)</math> mit <math>V = \{ v_1, \dotsc, v_n \}</math> und <math>E = \{ e_1, \dotsc, e_m \}</math> ist die Inzidenzmatrix <math>B = (b_{i, j})</math> definiert durch:
:<math>
b_{ij} := \begin{cases}
1, & \text{ falls } e_j = (v_i, x) \\
0, & \text{ falls } v_i \notin e_j \\
-1, & \text{ falls } e_j = (x, v_i)
\end{cases}
</math>

wobei <math>x</math> hier einen beliebigen Knoten darstellt.

Die Inzidenzmatrix eines [[Gerichteter Graph|gerichteten Graphen]] enthält also in jeder Spalte genau einmal die <math>1</math> (Startknoten) und einmal die <math>-1</math> (Endknoten). Alternativ werden Inzidenzmatrizen manchmal auch mit umgekehrtem Vorzeichen definiert, das heißt, <math> b_{ij}=-1 </math>, falls die [[Kante (Graphentheorie)|Kante]] <math> e_j </math> am [[Knoten (Graphentheorie)|Knoten]] <math> v_i </math> beginnt, und <math> b_{ij}=1 </math> falls die Kante <math> e_j </math> am Knoten <math> v_i </math> endet. Dies ist insbesondere zu beachten, wenn man [[Ungleichung|Ungleichungen]] betrachtet, die Inzidenzmatrizen enthalten.

== Beispiele ==

=== Ungerichtete Graphen ===

[[Datei:Inzidenzmatrix_exgraph.svg|alternativtext=|rechts|rahmenlos]]
Wir untersuchen nun als Beispiel den rechts stehenden [[Graph (Graphentheorie)|Graphen]], der dem [[Haus vom Nikolaus]] ähnelt, mit der in dem Bild angegebenen Nummerierung der [[Knoten (Graphentheorie)|Knoten]] und [[Kante (Graphentheorie)|Kanten]]. Um aus diesem Graphen eine Inzidenzmatrix zu erstellen, beginnen wir mit einer leeren Matrix. Diese enthält für den betrachteten Graphen <math>j=6</math> Spalten und <math>i=5</math> 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 <math>(e_1, e_2, \dotsc, e_6)</math>, 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:

<math>\begin{pmatrix}
1 & 0 & 0 & 0 & 1 & 0 \\
1 & 1 & 0 & 0 & 0 & 1 \\
0 & 1 & 1 & 0 & 0 & 0 \\
0 & 0 & 1 & 1 & 0 & 0 \\
0 & 0 & 0 & 1 & 1 & 1 \\
\end{pmatrix}</math>

oder als Tabelle formatiert:

{| class="wikitable"
|
! 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 [[Ungerichteter Graph|ungerichteten Graphen]] korrekt aufgebaut, dann muss in jeder Spalte (Kante) in Summe 2 stehen, da jede Kante exakt 2 Knoten verbindet.

Für nicht-schleifenfreie Graphen wird festgelegt: Ist eine Kante eine [[Schleife (Graphentheorie)|Schleife]], also eine Kante, die einen Knoten mit sich selbst verbindet, steht in der entsprechenden Zelle eine 2. Die Summe jeder Zeile entspricht der Anzahl Kantenenden an dem Knoten.<ref>{{Literatur |Autor = Manfred Brill |Titel = Mathematik für Informatiker. Einführung an praktischen Beispielen aus der Welt der Computer |Auflage = 2., völlig neu bearbeitete |Datum = 2005 |Verlag = Hanser Fachbuchverlag |Ort = München u. a. |ISBN = 3-446-22802-0 |Seiten = 161–169}}</ref>

=== Gerichtete Graphen ===

[[Datei:4node-digraph-embed.svg|alternativtext=|rechts|rahmenlos]]
Als Beispiel einer Inzidenzmatrix eines [[Gerichteter Graph|gerichteten Graphen]] betrachten wir nun den rechts stehenden [[Graph (Graphentheorie)|Graphen]]. Wieder nehmen wir die Nummerierung der [[Knoten (Graphentheorie)|Knoten]] als vorgegeben an. Die Kanten sind wie folgend nummeriert: <math> e_1=(1,2), e_2=(3,2), e_3=(3,1), e_4=(1,4), e_5=(2,4), e_6=(4,3).</math> Es ist <math> |E|=6=m</math> und <math> |V|=4=n</math>. Die Inzidenzmatrix ist also eine <math> 4 \times 6 </math>-Matrix:

<math>\begin{pmatrix}
1 & 0 &-1 & 1 & 0 & 0 \\
-1 &-1 & 0 & 0 & 1 & 0 \\
0 & 1 & 1 & 0 & 0 &-1 \\
0 & 0 & 0 &-1 &-1 & 1 \\
\end{pmatrix}</math>

oder als Tabelle formatiert:

{| class="wikitable"
|
! 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 (Mathematik)|Matrix]], die [[Graph (Graphentheorie)|Graphen]] beschreibt, ist die [[Laplace-Matrix]]. Es ist eine <math>n \times n</math>-Matrix, wobei <math>n</math> die Anzahl der [[Knoten (Graphentheorie)|Knoten]] ist. Die Koeffizienten ihrer Diagonale enthalten den [[Grad (Graphentheorie)|Grad]] der Knoten des Graphen, und die anderen Koeffizienten in Zeile <math>i</math> und in Spalte <math>j</math> sind gleich −1, wenn die Knoten <math>i</math> und <math>j</math> verbunden sind, und 0, wenn dies nicht der Fall ist.

Wenn <math>B(G)</math> die Inzidenzmatrix eines [[Gerichteter Graph|gerichteten Graphen]] <math>G</math> ist, können wir die Laplace-Matrix <math>L(G)</math> durch Multiplizieren von <math>B(G)</math> mit seiner [[Transponierte Matrix|transponierten Matrix]] <math>B^\mathrm{T}(G)</math> berechnen:
:<math>L(G) = B(G) \cdot B^\mathrm{T}(G)</math>

[[Datei:Incidence matrix oriented.svg|rechts|rahmenlos|220x220px]]
Zum Beispiel für den [[Gerichteter Graph|gerichteten Graphen]] in der nebenstehenden Abbildung:

<math>L(G) = \begin{pmatrix}
-1 & 0 & 0 & 0 & 1 & 0\\
1 & -1 & 0 & 0 & 0 & 1\\
0 & 1 & -1 & 0 & 0 & 0\\
0 & 0 & 1 & -1 & 0 & 0\\
0 & 0 & 0 & 1 & -1 & -1\\
\end{pmatrix} \cdot
\begin{pmatrix}
-1 & 1 & 0 & 0 & 0\\
0 & -1 & 1 & 0 & 0\\
0 & 0 & -1 & 1 & 0\\
0 & 0 & 0 & -1 & 1\\
1 & 0 & 0 & 0 & -1\\
0 & 1 & 0 & 0 & -1\\
\end{pmatrix} =
\begin{pmatrix}
2 & -1 & 0 & 0 & -1\\
-1 & 3 & -1 & 0 & -1\\
0 & -1 & 2 & -1 & 0\\
0 & 0 & -1 & 2 & -1\\
-1 & -1 & 0 & -1 & 3\\
\end{pmatrix}</math>

Die [[Adjazenzmatrix]] eines Graphen ist eine weitere [[Matrix (Mathematik)|Matrix]], die den [[Graph (Graphentheorie)|Graphen]] beschreibt. Es ist eine <math>n \times n</math>-Matrix, wobei <math>n</math> die Anzahl der [[Knoten (Graphentheorie)|Knoten]] ist. Die anderen Koeffizienten in Zeile <math>i</math> und in Spalte <math>j</math> sind gleich 1, wenn die Knoten <math>i</math> und <math>j</math> verbunden sind, und ansonsten 0. Für einen ungerichteten Graphen ist diese Matrix symmetrisch.

Die Gradmatrix eines Graphen ist eine <math>n \times n</math>-[[Diagonalmatrix]], die den [[Grad (Graphentheorie)|Grad]] jedes Knotens auflistet. Der [[Koeffizient]] in Zeile <math>i</math> und in Spalte <math>i</math> gibt den Grad des Knoten <math>i</math> an, alle anderen Koeffizienten sind 0.

Wenn <math>B(G)</math> die Inzidenzmatrix eines ungerichteten Graphen <math>G</math> ist, <math>A(G)</math> seine Adjazenzmatrix und <math>D(G)</math> seine Gradmatrix ist, dann gilt:
:<math>A(G) + D(G) = B(G) \cdot B^\mathrm{T}(G)</math>

[[Datei:Incidence matrix unoriented.svg|rechts|rahmenlos|220x220px]]
Zum Beispiel für den ungerichteten Graphen in der nebenstehenden Abbildung:

<math>A(G) + D(G) = \begin{pmatrix}
1 & 0 & 0 & 0 & 1 & 0\\
1 & 1 & 0 & 0 & 0 & 1\\
0 & 1 & 1 & 0 & 0 & 0\\
0 & 0 & 1 & 1 & 0 & 0\\
0 & 0 & 0 & 1 & 1 & 1\\
\end{pmatrix} \cdot
\begin{pmatrix}
1 & 1 & 0 & 0 & 0\\
0 & 1 & 1 & 0 & 0\\
0 & 0 & 1 & 1 & 0\\
0 & 0 & 0 & 1 & 1\\
1 & 0 & 0 & 0 & 1\\
0 & 1 & 0 & 0 & 1\\
\end{pmatrix} =
\begin{pmatrix}
2 & 1 & 0 & 0 & 1\\
1 & 3 & 1 & 0 & 1\\
0 & 1 & 2 & 1 & 0\\
0 & 0 & 1 & 2 & 1\\
1 & 1 & 0 & 1 & 3\\
\end{pmatrix}</math>

Indem wir die Diagonale von den anderen Werten isolieren, erhalten wir:

<math>A(G) = \begin{pmatrix}
0 & 1 & 0 & 0 & 1\\
1 & 0 & 1 & 0 & 1\\
0 & 1 & 0 & 1 & 0\\
0 & 0 & 1 & 0 & 1\\
1 & 1 & 0 & 1 & 0\\
\end{pmatrix}, \quad
D(G) = \begin{pmatrix}
2 & 0 & 0 & 0 & 0\\
0 & 3 & 0 & 0 & 0\\
0 & 0 & 2 & 0 & 0\\
0 & 0 & 0 & 2 & 0\\
0 & 0 & 0 & 0 & 3\\
\end{pmatrix}</math>

Der [[Kantengraph]] eines ungerichteten Graphen wird erhalten, indem seine [[Kante (Graphentheorie)|Kanten]] durch [[Knoten (Graphentheorie)|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 <math>B(G)</math> die Inzidenzmatrix eines ungerichteten Graphen <math>G</math> und <math>I_m</math> die [[Einheitsmatrix]] ist, können wir die [[Adjazenzmatrix]] <math>A(L(G))</math> seines [[Kantengraph|Kantengraphen]] folgendermaßen berechnen:
:<math>A(L(G)) = B(G) \cdot B^\mathrm{T}(G) - 2 \cdot I_m</math>

[[Datei:Line graph.svg|rechts|rahmenlos|202x202px]]
Zum Beispiel für den [[Kantengraph|Kantengraphen]] in der nebenstehenden Abbildung:

<math>A(L(G)) = \begin{pmatrix}
1 & 1 & 0 & 0 & 0\\
0 & 1 & 1 & 0 & 0\\
0 & 0 & 1 & 1 & 0\\
0 & 0 & 0 & 1 & 1\\
1 & 0 & 0 & 0 & 1\\
0 & 1 & 0 & 0 & 1\\
\end{pmatrix} \cdot
\begin{pmatrix}
1 & 0 & 0 & 0 & 1 & 0\\
1 & 1 & 0 & 0 & 0 & 1\\
0 & 1 & 1 & 0 & 0 & 0\\
0 & 0 & 1 & 1 & 0 & 0\\
0 & 0 & 0 & 1 & 1 & 1\\
\end{pmatrix} -
\begin{pmatrix}
2 & 0 & 0 & 0 & 0 & 0\\
0 & 2 & 0 & 0 & 0 & 0\\
0 & 0 & 2 & 0 & 0 & 0\\
0 & 0 & 0 & 2 & 0 & 0\\
0 & 0 & 0 & 0 & 2 & 0\\
0 & 0 & 0 & 0 & 0 & 2\\
\end{pmatrix} =
\begin{pmatrix}
0 & 1 & 0 & 0 & 1 & 1\\
1 & 0 & 1 & 0 & 0 & 1\\
0 & 1 & 0 & 1 & 0 & 0\\
0 & 0 & 1 & 0 & 1 & 1\\
1 & 0 & 0 & 1 & 0 & 1\\
1 & 1 & 0 & 1 & 1 & 0\\
\end{pmatrix}
</math>

== Verwendung ==

=== Speicherung von Graphen im Computer ===

Inzidenzmatrizen werden in der [[Informatik]] zur Speicherung von [[Graph (Graphentheorie)|Graphen]] verwendet. Die Inzidenzmatrix eines Graphen mit <math>n</math> [[Knoten (Graphentheorie)|Knoten]] und <math>m</math> [[Kante (Graphentheorie)|Kanten]] benötigt einen Speicherplatz von <math>\mathcal{O}(n\cdot m)</math>. Da die [[Platzkomplexität]] von [[Adjazenzmatrix|Adjazenzmatrizen]] <math>\mathcal{O}(n^2)</math> beträgt, sind Inzidenzmatrizen, sollte es weniger Kanten als Knoten geben, speicherplatztechnisch effizienter.

=== Spektrale Graphentheorie ===

Des Weiteren finden Inzidenzmatrizen Anwendung in der [[Spektrale Graphentheorie|spektralen Graphentheorie]], wo versucht wird, aufgrund gewisser Eigenschaften der Inzidenzmatrix Rückschlüsse auf die Eigenschaften des repräsentierten [[Graph (Graphentheorie)|Graphen]] zu ziehen.

=== Optimierung ===

Die Inzidenzmatrix eines ungerichteten [[Bipartiter Graph|bipartiten Graphen]] ist eine [[total unimodulare Matrix]], genauso wie die eines [[Gerichteter Graph|Digraphen]]. Daher lässt sich unter gewissen Voraussetzungen die Ganzzahligkeit der Lösung eines [[Lineare Optimierung|linearen Optimierungsproblems]] zeigen, wenn die zulässige Menge durch eine der vorhin genannten Inzidenzmatrizen definiert wird. Insbesondere stellt dies eine Verbindung zwischen [[Diskrete Optimierung|diskreter Optimierung]] und [[Lineare Optimierung|linearer Optimierung]] her.

== Literatur ==

* {{Literatur |Autor=[[Peter Knabner]], [[Wolf Barth (Mathematiker)|Wolf Barth]] |Titel=Lineare Algebra. Grundlagen und Anwendungen |Reihe=Springer-Lehrbuch |Verlag=Springer Spektrum |Ort=Berlin u. a. |Datum=2013 |ISBN=978-3-642-32185-6}}
* {{Literatur |Autor=[[Reinhard Diestel]] |Titel=Graphentheorie |Auflage=4. |Verlag=Springer |Ort=Heidelberg u. a. |Datum=2010 |ISBN=978-3-642-14911-5}}

== Einzelnachweise ==

<references />

{{Normdaten|TYP=s|GND=4815731-4}}

[[Kategorie:Grundbegriff (Graphentheorie)]]
[[Kategorie:Datenstruktur]]

Inzidenzmatrix - Versionsgeschichte

imported>Alexander Nikolaj Block: /* growthexperiments-addlink-summary-summary:1|1|0 */