Inzidenzmatrix - LinkFang.de





Inzidenzmatrix


Dieser Artikel behandelt die Inzidenzmatrix von Graphen. Eine allgemeinere Sichtweise wird im Artikel zu Inzidenzstrukturen beschrieben.

Eine Inzidenzmatrix (auch Knoten-Kanten-Matrix) eines Graphen ist eine Matrix, welche die Beziehungen der Knoten und Kanten des Graphen speichert. Besitzt der Graph [math]n[/math] Knoten und [math]m[/math] Kanten ist seine Inzidenzmatrix eine [math]n \times m[/math]-Matrix. Der Eintrag in der i-ten Zeile und j-ten Spalte gibt an, ob der i-te Knoten teil der j-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 n und die Kanten von 1 bis m durchnummeriert sind.

Definition

Ungerichtete Graphen

Für einen schleifenfreien ungerichteten Graphen [math]G = (V, E)[/math] mit [math]V = \lbrace v_1, ..., v_n \rbrace[/math] und [math]E = \lbrace e_1, ..., e_m \rbrace[/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, gerichteten Graphen [math]G = (V, E)[/math] mit [math]V = \lbrace v_1, ..., v_n \rbrace[/math] und [math]E = \lbrace e_1, ..., e_m \rbrace[/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 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 auch manchmal mit umgekehrtem Vorzeichen definiert, heißt [math] b_{ij}=-1 [/math] falls die Kante [math] e_j [/math] am 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 Ungleichungen betrachtet, die Inzidenzmatrizen enthalten.

Beispiele

Ungerichtete Graphen

Wir untersuchen nun als Beispielgraph 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 [math]j=6[/math] Spalten und [math]i=5[/math] Zeilen. Die Kanten werden in die Spalten eingetragen und die Ecken 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,\ldots,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} e_1 & e_2 & e_3 & e_4 & e_5 & e_6\\ 1&0&0&0&1&0& v_1\\ 1&1&0&0&0&1& v_2\\ 0&1&1&0&0&0& v_3\\ 0&0&1&1&0&0& v_4\\ 0&0&0&1&1&1& v_5\\ \end{pmatrix}[/math]

Ist die Inzidenzmatrix 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

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: [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} e_1 & e_2 & e_3 & e_4 & e_5 & e_6\\ 1 & 0&-1& 1& 0& 0& v_1\\ -1&-1& 0& 0& 1& 0& v_2\\ 0 & 1& 1& 0& 0&-1& v_3\\ 0 & 0& 0&-1&-1& 1& v_4\\ \end{pmatrix}[/math]

Die Inzidenzmatrix ist korrekt aufgebaut: In jeder Spalte stehen zwei Nichtnulleinträge, welche sich zu Null addieren.

Verwendung

Speicherung von Graphen im Computer

Inzidenzmatrizen werden in der Informatik zur Speicherung von Graphen verwendet. Die Inzidenzmatrix eines Graphen mit [math]n[/math] Knoten und [math]m[/math] Kanten benötigt einen Speicher von [math]\mathcal{O}(n\cdot m)[/math].

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

Einzelnachweise

  1. Manfred Brill: Mathematik für Informatiker. Einführung an praktischen Beispielen aus der Welt der Computer. 2., völlig neu bearbeitete Auflage. Hanser Fachbuchverlag, München u. a. 2005, ISBN 3-446-22802-0, S. 161–169.

Kategorien: Datenstruktur | Grundbegriff (Graphentheorie)

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Inzidenzmatrix (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.