Matriz de incidencia

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

Una matriz de incidencia es una representación de la relación entre dos conjuntos de elementos mediante una matriz binaria compuesta por ceros "0" o unos "1". La matriz de incidencia es una matriz de tipo lógica (boleana o binaria) y establece una conexión inequívoca entre los conjuntos. A los cuartiles que representan la relación entre los elementos de los conjuntos se les denomina relación de incidencia.

Para comprender mejor su estructura, consideremos dos clases: X y Y. La matriz de incidencia se organiza de tal manera que cada fila corresponde a un elemento del conjunto X, mientras que cada columna representa un elemento del conjunto Y. Así, la matriz se compone de filas y columnas que cruzan estos dos conjuntos.

En el cruce de una fila n de X con una columna m de Y, encontramos un valor clave: si este valor es 1, indica que el elemento n del conjunto X está relacionado o incide con el elemento m del conjunto Y. Por el contrario, un valor 0 en esta intersección señala que no existe tal relación o incidencia entre los elementos n y m.

Este concepto es fundamental para las matemáticas en general, ya que una matriz de incidencia es una herramienta matemática versátil y efectiva para representar y analizar las relaciones entre dos conjuntos de elementos.

Es importante destacar que existen variaciones en la forma en que se puede configurar y utilizar una matriz de incidencia, dependiendo del contexto específico y de las necesidades del análisis. Estas variaciones permiten una adaptabilidad significativa de la matriz de incidencia a diferentes campos y aplicaciones de las matemáticas.

HSD

Teoría de grafos

La matriz de incidencia es una representación gráfica común en la teoría de grafos. Es diferente a una matriz de adyacencia, que codifica la relación de pares vértice-vértice.

Grafos dirigidos y no dirigidos

En la teoría de grafos, un grafo no dirigido tiene dos tipos de matrices de incidencia: orientadas y no orientadas.

La matriz de incidencia no orientada (o simplemente matriz de incidencia) de un grafo no dirigido es una $nveces m$ matriz B, donde n y m son los números de vértices y aristas respectivamente, tal que ${ estilo de visualización B_ {ij} = 1}$ si el vértice $v_{{yo}}$ y la arista ${ estilo de visualización e_ {j}}$ son incidentes y 0 en caso contrario.

Por ejemplo, la matriz de incidencia del gráfico no dirigido que se muestra a la derecha es una matriz que consta de 4 filas (correspondientes a los cuatro vértices, 1–4) y 4 columnas (correspondientes a los cuatro bordes, ${displaystyle e_{1},e_{2},e_{3},e_{4}}$ ):

{displaystyle {begin{bmatrix}1&1&1&0\1&0&0&0\0&1&0&1\0&0&1&1\end{bmatrix}}.}

Si miramos la matriz de incidencia, vemos que la suma de cada columna es igual a 2. Esto se debe a que cada arista tiene un vértice conectado a cada extremo.

La matriz de incidencia de un grafo dirigido es una $nveces m$ matriz B donde n y m son el número de vértices y aristas respectivamente, tal que ${displaystyle B_{ij}=-1}$ si la arista ${ estilo de visualización e_ {j}}$ sale del vértice $v_{{yo}}$ , 1 si entra en el vértice $v_{{yo}}$ y 0 en caso contrario (muchos autores usan la convención de signos opuestos).

La matriz de incidencia orientada de un gráfico no dirigido es la matriz de incidencia, en el sentido de gráficos dirigidos, de cualquier orientación del gráfico. Es decir, en la columna de la arista e, hay un 1 en la fila correspondiente a un vértice de e y un −1 en la fila correspondiente al otro vértice de e, y todas las demás filas tienen 0. La matriz de incidencia orientada es único hasta la negación de cualquiera de las columnas, ya que negar las entradas de una columna corresponde a invertir la orientación de una arista.

La matriz de incidencia no orientada de un grafo G está relacionada con la matriz de adyacencia de su grafo lineal L (G) por el siguiente teorema: ${displaystyle A(L(G))=B(G)^{textsf {T}}B(G)-2I_{m}.}$

donde A (L (G)) es la matriz de adyacencia del gráfico lineal de G, B (G) es la matriz de incidencia e I _m es la matriz identidad de dimensión m.

La matriz laplaciana discreta (o matriz de Kirchhoff) se obtiene a partir de la matriz de incidencia orientada B (G) mediante la fórmula ${displaystyle B(G)B(G)^{textsf {T}}.}$

El espacio del ciclo integral de un grafo es igual al espacio nulo de su matriz de incidencia orientada, vista como una matriz sobre los números enteros o reales o complejos. El espacio del ciclo binario es el espacio nulo de su matriz de incidencia orientada o no orientada, vista como una matriz sobre el campo de dos elementos.

Grafos firmados y bidireccionados

La matriz de incidencia de un grafo con signo es una generalización de la matriz de incidencia orientada. Es la matriz de incidencia de cualquier grafo bidirigido que orienta el grafo con signo dado. La columna de una arista positiva tiene un 1 en la fila que corresponde a un extremo y un −1 en la fila que corresponde al otro extremo, al igual que una arista en un gráfico ordinario (sin signo). La columna de un borde negativo tiene un 1 o un −1 en ambas filas. Las propiedades del gráfico lineal y de la matriz de Kirchhoff se generalizan a gráficos con signo.

Multigrafos

Las definiciones de matriz de incidencia se aplican a gráficos con bucles y múltiples aristas. La columna de una matriz de incidencia orientada que corresponde a un bucle es todo cero, a menos que el gráfico esté firmado y el bucle sea negativo; entonces la columna es todo cero excepto ±2 en la fila de su vértice incidente.

Grafos ponderados

Un gráfico ponderado se puede representar usando el peso del borde en lugar de un 1. Por ejemplo, la matriz de incidencia del gráfico de la derecha es:

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

Hipergrafos

Debido a que los bordes de los gráficos ordinarios solo pueden tener dos vértices (uno en cada extremo), la columna de una matriz de incidencia para gráficos solo puede tener dos entradas distintas de cero. Por el contrario, una hipergrafía puede tener múltiples vértices asignados a un borde; así, una matriz general de enteros no negativos describe una hipergrafía.

Estructuras de incidencia

La matriz de incidencia de una estructura de incidencia C es una matriz B p × q (o su traspuesta), donde p y q son el número de puntos y rectas respectivamente, tal que B _i_,_j = 1 si el punto pi _y la recta L _j son incidentes y 0 en caso contrario. En este caso, la matriz de incidencia es también una matriz de biadyacencia del gráfico de Levi de la estructura. Como hay una hipergrafía para cada gráfica de Levi, y viceversa, la matriz de incidencia de una estructura de incidencia describe una hipergrafía.

Geometrías finitas

Un ejemplo importante es una geometría finita. Por ejemplo, en un plano finito, X es el conjunto de puntos e Y es el conjunto de líneas. En una geometría finita de mayor dimensión, X podría ser el conjunto de puntos e Y podría ser el conjunto de subespacios de dimensión uno menos que la dimensión del espacio total (hiperplanos); o, más generalmente, X podría ser el conjunto de todos los subespacios de una dimensión dy Y el conjunto de todos los subespacios de otra dimensión e, con incidencia definida como contención.

Politopos

De manera similar, la relación entre celdas cuyas dimensiones difieren en uno en un politopo, puede representarse mediante una matriz de incidencia.

Diseños de bloques

Otro ejemplo es un diseño de bloque. Aquí X es un conjunto finito de "puntos" e Y es una clase de subconjuntos de X, llamados "bloques", sujetos a reglas que dependen del tipo de diseño. La matriz de incidencia es una herramienta importante en la teoría de diseños de bloques. Por ejemplo, se puede usar para probar la desigualdad de Fisher, un teorema fundamental de 2 diseños incompletos balanceados (BIBD), que el número de bloques es al menos el número de puntos. Considerando los bloques como un sistema de conjuntos, el permanente de la matriz de incidencia es el número de sistemas de representantes distintos (SDRs).

Contenido relacionado

Más resultados...