Matriu d'incidència

En matemàtiques, una matriu d'incidència és una matriu que mostra la relació entre dues classes d'objectes. Si la primera classe és X i la segona és Y, la matriu té una fila per a cada element de X i una columna per a cada element de Y. L'entrada de la fila x i la columna y és 1 si els elements x i y estan relacionats (hom en diu incidents, en aquest context) i 0 si no ho estan.

Teoria de grafs

Les matrius d'incidència s'utilitzen amb freqüència a la teoria de grafs.

Grafs dirigits i no dirigits

Un graf no dirigit.

En teoria de grafs, un graf no dirigit té dues classes de matrius d'incidència: orientada i no orientada.

La matriu d'incidència no orientada (o simplement matriu d'incidència) d'un graf no dirigit és una matriu B de dimensions n × m, on n i m són els nombres de vèrtexs i arestes respectivament, tal que B_i,j = 1 si el vèrtex v_i i l'aresta e_j són incidents i 0 altrament.

Per exemple, la matriu d'incidència del graf no dirigit de la dreta és una matriu que consisteix en 4 files (corresponents al quatre vèrtexs, 1–4) i 4 columnes (corresponents a les quatre arestes, e1–e4):

e1 e₂ e₃ e₄ 1 1 1 1 0 2 1 0 0 0 3 0 1 0 1 4 0 0 1 1

=

${\begin{pmatrix}1&1&1&0\\1&0&0&0\\0&1&0&1\\0&0&1&1\\\end{pmatrix}}.$

Si hom observa la matriu d'incidència, es pot veure que la suma de cada columna és igual a 2. Això és perquè cada aresta té un vèrtex connectat en cada extrem.

La matriu d'incidència d'un graf dirigit és una matriu B de dimensions n × m, on n i m són el nombre de vèrtexs i arestes respectivament, tal que B_i,j = −1 si l'aresta e_j surt del vèrtex v_i, 1 si entra al vèrtex v_i i 0 altrament (molts autors utilitzen una convenció de signes contrària a aquesta).

La matriu d'incidència orientada d'un graf no dirigit és la matriu d'incidència, en el sentit dels grafs dirigits, de qualsevol orientació del graf. Això és, en la columna de l'aresta e hi ha un 1 en la fila que correspon a un vèrtex de e i un −1 en la fila que correspon a l'altre vèrtex de e, i totes les altres files tenen un 0. La matriu d'incidència orientada és única llevat de canviar de signe qualsevol de les columnes, ja que canviar de signe les entrades d'una columna correspon a invertir l'orientació d'una aresta.

La matriu d'incidència no orientada d'un graf G està relacionada amb la matriu d'adjacència del seu graf línia L(G) pel teorema següent:

$A(L(G))=B(G)^{\textsf {T}}B(G)-2I_{m}.$

on A(L(G)) és la matriu d'adjacència del graf línia de G, B(G) és la matriu d'incidència, i I_m és la matriu identitat de dimensió m.

El Laplacià discret (o matriu de Kirchhoff) s'obté a partir de la matriu d'incidència orientada B(G) mitjançant la fórmula

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

L'espai de cicles integral d'un graf és igual al nucli de la seva matriu d'incidència orientada, vista com una matriu sobre els enters o els reals o els complexos. L'espai de cicles binari és el nucli de la seva matriu d'incidència orientada o no orientada, vista com una matriu sobre el cos de dos elements.

Grafs amb signes i grafs bidirigits

La matriu d'incidència d'un graf amb signe és una generalització de la matriu d'incidència orientada. És la matriu d'incidència de qualsevol graf bidirigit que orienta el graf amb signe donat. La columna d'una aresta positiva té un 1 en la fila que correspon a un extrem i un −1 en la fila que correspon a l'altre extrem, de la mateixa manera que una aresta en un graf ordinari (sense signe). La columna d'una aresta negativa conté un 1 o un −1 en ambdues files. Les propietats del graf de línia i de la matriu de Kirchhoff es generalitzen al cas de grafs amb signe.

Multigrafs

Les definicions de matriu d'incidència també es poden aplicar a grafs amb bucles i amb arestes múltiples. La columna d'una matriu d'incidència orientada corresponent a un bucle té totes les entrades a zero, llevat que el graf sigui amb signe i el bucle sigui negatiu; en tal cas, la columna és tota zero excepte ±2 en la fila del seu vèrtex incident.

Hipergrafs

Com que les arestes dels grafs ordinaris només poden tenir dos vèrtexs (un a cada extrem), la columna d'una matriu d'incidència per a grafs només poden tenir dues entrades diferents de 0. En canvi, en un hipergraf pot haver-hi múltiples vèrtexs assignats a una aresta; així, una matriu general amb entrades enteres i no-negatives pot descriure un hipergraf.

Estructures d'incidència

La matriu d'incidència d'una estructura d'incidència C és una matriu B de dimensions p × q (o la seva transposada), on p i q són el nombre de punts i línies respectivament, tal que B_i,j = 1 si el punt p_i i la línia L_j són incidents i 0 altrament. En aquest cas, la matriu d'incidència és també una matriu de biadjacència del graf de Levi de l'estructura. Com que existeix un hipergraf per a tot graf de Levi, i viceversa, la matriu d'incidència d'una estructura d'incidència descriu un hipergraf.

Geometries finites

Un exemple important és una geometria finita. Per exemple, en un pla finit, X és el conjunt de punts i Y és el conjunt de línies. En una geometria finita de dimensió més alta, X podria ser el conjunt de punts i Y podria ser el conjunt de subespais de dimensió una menys que la dimensió de l'espai sencer (hiperplans); o, més generalment, X podria ser el conjunt de tots els subespais d'una certa dimensió d i Y el conjunt de tots els subespais d'una altra dimensió e, amb la incidència definida com a restricció.

Polítops

De la mateixa manera, es pot representar amb una matriu d'incidència la relació entre les cel·les d'un polítop amb dimensions que difereixen en 1.

Dissenys de blocs

Un altre exemple és un disseny de blocs. Aquí, X és un conjunt finit de "punts" i Y és una classe de subconjunts de X, anomenats "blocs", subjecta a regles que depenen segons el tipus de disseny. La matriu d'incidència és una eina important en la teoria de dissenys de blocs. Per exemple, es pot utilitzar per demostrar la desigualtat de Fisher, un teorema fonamental en dissenys de blocs incomplets balancejats, que diu que el nombre de blocs és com a mínim el nombre de punts.

Bibliografia

• Diestel, Reinhard. Springer-Verlag. Graph Theory. 173. 3a, 2005 (Graduate Texts in Mathematics). ISBN 3-540-26183-4. 
• Gross, Jonathan L.; Yellen, Jay. Graph Theory and its applications. 2a, 2006, p. 97-98.