Inzidenzmatrix

Eine Inzidenzmatrix eines Graphen ist eine Matrix, welche die Beziehungen der Knoten und Kanten des Graphen speichert. Wenn der Graph ${\displaystyle n}$ Knoten und ${\displaystyle m}$ Kanten besitzt, ist seine Inzidenzmatrix eine ${\displaystyle n\times m}$-Matrix. Der Eintrag in der ${\displaystyle i}$-ten Zeile und ${\displaystyle j}$-ten Spalte gibt an, ob der ${\displaystyle i}$-te Knoten Teil der ${\displaystyle 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 ${\displaystyle n}$ und die Kanten von 1 bis ${\displaystyle m}$ durchnummeriert sind.