Matriz de incidencia

En matemáticas, unha **matriz de incidencia** é unha matriz lóxica que mostra a relación entre dúas clases de obxectos, normalmente chamada relación de incidencia. Se a primeira clase é *X* e a segunda é *Y*, a matriz ten unha fila para cada elemento de *X* e unha columna para cada asignación de *X* a *Y*. 

A entrada na fila *x* e columna *y* é 1 se o vértice *x* forma parte (denominado *incidente* neste contexto) do mapa que corresponde a *y*, e 0 se non o é. 

Hai algunha variante; ver a continuación.

## Teoría de grafos 
A matriz de incidencia é unha representación gráfica común na teoría de grafos. É diferente a unha matriz de adxacencia, que codifica a relación de pares vértice-vértice.

### Grafos non orientados e orientados 
miniatura|256x256px| Un grafo non orientado.
Na teoría de grafos un grafo non orientado ten dous tipos de matrices de incidencia: non orientadas e orientadas.

A *matriz de incidencia non orientada* (ou simplemente *matriz de incidencia*) dun grafo non orientado é a  matriz *B n\times m*, onde *n* e *m* son os números de vértices e arestas respectivamente, de tal forma que

: B_{ij}=\left\{\begin{array}{rl}\,1 & \text{se o vértice }v_i\text{ é incidente con aresta }e_j, \\ 0 & \text{noutro caso.}\end{array}\right.

Por exemplo, a matriz de incidencia do grafo non orientado que se mostra á dereita é unha matriz formada por 4 filas (correspondentes aos catro vértices, 1-4) e 4 columnas (correspondentes ás catro arestas, e_{1},e_{2},e_{3},e_{4}):

| =
| 
\begin{bmatrix}
 1 & 1 & 1 & 0 \\
 1 & 0 & 0 & 0 \\
 0 & 1 & 0 & 1 \\
 0 & 0 & 1 & 1 \\
\end{bmatrix}.

|}
Se observamos a matriz de incidencia, vemos que a suma de cada columna é igual a 2. Isto débese a que cada aresta ten un vértice ligado a cada extremo.

A *matriz de incidencia* dun grafo orientado é a  matriz *B* n\times m onde *n* e *m* son o número de vértices e arestas respectivamente, de xeito que

: B_{ij}=\left\{\begin{array}{rl}
{-1} & \text{se a aresta }e_j\text{ sae do vértice }v_i, \\
\phantom{-}1 & \text{se a aresta }e_j\text{ entra no vértice }v_i, \\
\phantom{-}0 & \text{noutro caso.}
\end{array}\right.

(Moitos autores usan a convención de signo oposto).

A matriz de incidencia non orientada dun grafo *G* está relacionada coa matriz de adxacencia da súa grafo liña *L*(*G*) polo seguinte teorema:

: A(L(G)) = B(G)^\textsf{T}B(G) - 2I_m.

onde *A*(*L*(*G*)) é a matriz de adxacencia do grafo liña de *G*, *B*(*G*) é a matriz de incidencia e *I**m* é a matriz identidade da dimensión *m*.

O laplaciano discreto (ou matriz de Kirchhoff) obtense a partir da matriz de incidencia orientada *B*(*G*) mediante a fórmula

: B(G) B(G)^\textsf{T}.

### Multigrafos 
As definicións de matriz de incidencia aplícanse a grafos con bucles e arestas múltiples. A columna dunha matriz de incidencia orientada que corresponde a un bucle é toda cero, a non ser que o grafo estea con signo e o bucle sexa negativo; entón a columna é toda cero agás ±2 na fila do seu vértice incidente.

### Grafos ponderados 
miniatura| Un grafo ponderado non orientado
Un  grafo ponderado pódese representar usando o peso da aresta en lugar de 1. Por exemplo, a matriz de incidencia do grafo da dereita é:

| =
| 
\begin{bmatrix}
 2 & 1 & 5 & 0 \\
 2 & 0 & 0 & 0 \\
 0 & 1 & 0 & 6 \\
 0 & 0 & 5 & 6 \\
\end{bmatrix}.

|}

## Estruturas de incidencia 
A *matriz de incidencia* dunha estrutura de incidencia *C* é unha matriz  *B*  (ou a súa transposta), onde *p* e *q* son o número de *puntos* e *liñas* respectivamente, de tal forma que  se o punto *p**i* e a liña *L**j* son incidentes e 0 en caso contrario. 

Neste caso, a matriz de incidencia tamén é unha matriz de biadjacencia do grafo de Levi da estrutura. Como hai un hipergrafo para cada grafo de Levi, e *viceversa*, a matriz de incidencia dunha estrutura de incidencia describe un hipergrafo.

### Xeometrías finitas 
Un exemplo importante é unha xeometría finita. Por exemplo, nun plano finito, *X* é o conxunto de puntos e *Y* é o conxunto de liñas. 

Nunha xeometría finita de dimensión superior, *X* podería ser o conxunto de puntos e *Y* podería ser o conxunto de subespazos de dimensión un menos que a dimensión de todo o espazo (hiperplanos); ou, de xeito máis xeral, *X* podería ser o conxunto de todos os subespazos dunha dimensión *d* e *Y* o conxunto de todos os subespazos doutra dimensión *e*, con "incidencia" definida como "estar contido en".

### Polítopos
De xeito similar, a relación entre celas cuxas dimensións difiren nun polítopo, pódese representar mediante unha matriz de incidencia.
## Notas 
## Véxase tamén 
### Bibliografía 
* 
* Jonathan L Gross, Jay Yellen, *Graph Theory and its applications*, second edition, 2006 (p 97, Incidence Matrices for undirected graphs; p 98, incidence matrices for digraphs)

### Outros artigos 
* Relación binaria
* Matriz lóxica
* Camiño (teoría de grafos)
### Ligazóns externas 
*