Inzidenzmatrix

Eine Inzidenzmatrix ist eine Möglichkeit zur Repräsentation eines Graphen im Computer. Die Inzidenzmatrix B=(b_i,j) ist eine n×m-Matrix, wobei n=|V| die Anzahl der Knoten und m=|E| die Anzahl der Kanten eines Graphen G=(V, E) ist.

Inzidenzmatrix eines ungerichteten Graphen

Für einen ungerichteten Graphen G=(V, E) mit V={v₁, ...,v_n} und E={e₁, ...,e_m} ist die Inzidenzmatrix B=(b_i,j) definiert durch:

$b_{ij} := \left\{\begin{matrix} 1, & \mbox{falls } v_i \in e_j, \\ 0, & \mbox{sonst}. \end{matrix} \right.$

Beispiel

Der im Bild dargestellte Graph hat beispielsweise die folgende Inzidenzmatrix:

Bild:Inzidenzmatrix_exgraph.png $\Leftrightarrow\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}$

Inzidenzmatrix eines gerichteten Graphen

Für einen schleifenfreien gerichteten Graphen G=(V, E) mit V={v₁, ...,v_n} und E={e₁, ...,e_m} ist die Inzidenzmatrix B=(b_i,j) definiert durch:

$b_{ij} := \left\{\begin{matrix} 1, & \mbox{falls } e_j=(v_i,x), \\ 0, & \mbox{falls } v_i \notin e_j, \\ -1, & \mbox{falls } e_j=(x,v_i). \end{matrix} \right.$

wobei x hier einen beliebigen Knoten darstellt.

Für weitere Informationen siehe auch Repräsentation von Graphen im Computer, Adjazenzmatrix, Adjazenzliste.

Inzidenzmatrix

Inzidenzmatrix eines ungerichteten Graphen

Beispiel

Inzidenzmatrix eines gerichteten Graphen

See also: Inzidenzmatrix, Adjazenzliste, Adjazenzmatrix, Computer, Gerichteter Graph, Graph (Graphentheorie), Kante (Graphentheorie), Knoten (Graphentheorie), Repräsentation von Graphen im Computer, Schleifenfreier Graph