|
Eine Inzidenzmatrix ist eine Möglichkeit zur Repräsentation eines Graphen im Computer. Die Inzidenzmatrix
B=(bi,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={v1, ...,vn} und E={e1, ...,em}
ist die Inzidenzmatrix B=(bi,j) definiert durch:
Beispiel
Der im Bild dargestellte Graph hat beispielsweise die folgende Inzidenzmatrix:
 
Inzidenzmatrix eines gerichteten Graphen
Für einen schleifenfreien gerichteten Graphen G=(V, E) mit
V={v1, ...,vn} und E={e1, ...,em} ist die
Inzidenzmatrix B=(bi,j) definiert durch:
wobei x hier einen beliebigen Knoten darstellt.
Für weitere Informationen siehe auch Repräsentation von Graphen im Computer, Adjazenzmatrix, Adjazenzliste.
|
Startseite 
Bookmark setzen
Sitemap
Impressum
Lexikon Eintrag Drucken
Dokument als PDF downloaden