WikiDer > Inzidenzmatrix

Das Inzidenzmatrix ist ein Matrix, die unter anderem in der projektive Geometrie kann benutzt werden um projektive Ebene beschreiben.

Eine Inzidenzmatrix kann sein Informatik eine kompakte Darstellung von a Anzahl Formen. Die Inzidenzmatrix eines Graphen mit nein Knöpfe und p hat Seiten ${displaystyle {mathcal {O}}(ncdot p)}$ Speicherplätze benötigt. Für 'dünne' Graphen Graphen mit vielen Knoten, aber relativ wenigen Seiten, also p viel kleiner als nein, dies könnte ein Vorteil gegenüber einer Darstellung wie sein Bogenmatrix, Das ${displaystyle {mathcal {O}}(n^{2})}$ belegt Speicher.

Projektive Geometrie

Es kann für ein projektive Ebene, zum Beispiel für die Fan-Flugzeug, zeigt eine Inzidenzmatrix an, welche Punkte auf welchen Linien liegen. Punkte und Linien müssen dazu nummeriert werden, einer an Ort und Stelle ( ich, j ) bedeutet den Punkt mit der Zeilennummer ich in der Zeile mit der Spaltennummer ja ist eine Null, die es nicht ist. Die Einfallsmatrix ist für die Fano-Ebene symmetrisch, Punkte und Linien können vertauscht werden.

Ungerichtete Zählung

Inzidenzmatrizen finden Sie im Graphentheorie werden verwendet, um einen Graphen zu beschreiben. Für einen ungerichteten, ungewichteten Graphen mit nein Knöpfe und p Bögen, die Inzidenzmatrix ist a nein Biene p Matrix, in der das Element auf dem ich-die Reihe und ja- Die Spalte ist gleich:

• 1 wenn knoten ${displaystyle v_{i}}$ ein Ende des Bogens ${displaystyle x_{j}}$;
• 2 wenn der Bogen ${displaystyle x_{j}}$ eine Schlaufe ist aus Knoten ${displaystyle v_{i}}$ zu ${displaystyle v_{i}}$;
• 0 Andernfalls.

Beispiel: Angenommen, die Bögen in der folgenden Grafik sind wie folgt nummeriert:

1. zwischen 1 und 1
2. zwischen 1 und 2
3. zwischen 1 und 5
4. zwischen 2 und 5
5. zwischen 2 und 3
6. zwischen 5 und 4
7. zwischen 3 und 4
8. zwischen 4 und 6

dann sieht die Inzidenzmatrix so aus:

Beschriftete Anzahl	Inzidenzmatrix
	${displaystyle { egin{pmatrix}2&1&1&0&0&0&0&0/0&1&0&1&1&0&0&0/0&0&0&0&1&0&1&0/0&0&0&0&0&1&1&1/0&0&1&1&0&1&0&0&0&0&0}{$

Die Summe jeder Spalte ist gleich 2, da jeder Bogen zwei Knoten verbindet.

Die Summe der ich-die Zeile in der Inzidenzmatrix ist der Grad des Knotens ich, dies ist die Anzahl der Bögen, die sich in diesem Knoten treffen. Eine Schleife wird zweimal gezählt. Die Gradmatrix des Graphen ist die nein Biene nein-diagonale Matrix mit dem Grad jedes Knotens auf der Diagonalen, hier ist die Matrix:

${displaystyle D={ egin{pmatrix}4&0&0&0&0&0/0&3&0&0&0&0/0&0&2&0&0&0/0&0&0&3&0&0/0&0&0&0&3&0/0&0&0&0&0&1/end{pmatrix}}}$

Regie zählen

Für einen gerichteten Graphen, in dem jeder Bogen einen Start- und einen Endknoten hat, ist das Element auf der ich-die Reihe und ja-die Spalte in der Inzidenzmatrix ist gleich:

• 1 wenn knoten ${displaystyle v_{i}}$ der Anfangsknoten ist vom Bogen ${displaystyle x_{j}}$;
• -1 wenn knoten ${displaystyle v_{i}}$ der Endknoten ist vom Bogen ${displaystyle x_{j}}$;
• 0 Andernfalls.

Manchmal wird es umgekehrt gesagt, -1 wenn der Bogen den Knoten verlässt und 1 wenn der Bogen im Knoten ankommt.

Die Summe einer Spalte in der Inzidenzmatrix ist nun immer gleich Null. Wenn es in einem gerichteten Graphen eine Schleife gibt, besteht die entsprechende Spalte ausschließlich aus Nullen.