Matriu de distàncies

En Matemàtiques, Ciències de la computació i teoria de grafos, una matriu de distàncies és una Matriu quadrada els elements de la qual representen les Distàncies entre els punts, presos per parells, d'un conjunt. Depenent de la seua aplicació, la distància usada per a definir esta matriu pot o no ser una mètrica. Es tracta, per lo tant, d'una matriu simètrica de tamany $N\times N$ (donat un conjunt de $N$ punts en l'Espai euclídeo) contenint número real no negatius com a elements. El número N de parells de punts, (N-1)/2, és el número d'elements independents en la matriu de distàncies.

Les matrius de distàncies estan relacionades en les matrius de adyacencia, diferenciant-se en que les últimes només informen sobre quins vèrtiços estan conectats, pero no especifiquen costs o distàncies entre els vèrtiços; ademés, cada element d'una matriu de distàncies és més chicotet quant més propencs es troben els punts, mentres que vèrtiços propencs (conectats) produïxen elements majors en una matriu de adyacencia.

Matriu de distàncies no mètriques

En general, una matriu de distàncies és una matriu de adyacencia ponderada d'alguna gràfica. En una ret, una gràfica dirigida en pesos assignats en les seues arestes, la distància entre dos nodos de la ret es pot definir com el mínim de les sumes dels pesos en els camins més curts que unixen els dos nodos. Esta funció de distància, encara que ben definida, no és una mètrica. No és necessari que hi haja restriccions en els pesos, a banda de la necessitat de poder combinar-los i comparar-los, per lo que els pesos negatius s'utilisen en algunes aplicacions. Ya que els camins estan dirigits, la simetria no es pot garantisar, i si els cicles existixen, la matriu de distància pot no ser hueca.

Una formulació algebraica de lo anterior es pot obtindre per mig de l'àlgebra min-plus. La multiplicació de la matriu en este sistema es definix de la següent manera: Donades dos matrius de tamany $n\times n$, $A=(a_{ij})$ i $B=(b_{ij})$, el seu producte de distància $C=(c_{ij})=AB$ es definix com una matriu de tamany $n\times n$ tal que

$c_{ij}={\min }_{k=1}^n\{a_{ik}+b_{kj}\}$

Tinga en conte que els elements fòra de la diagonal que no estan conectats directament tindran que ajustar-se a l'infinit o un valor gran adequat per a que les operacions min-plus funcionen correctament. Un zero en estes ubicacions serà interpretat incorrectament com una aresta sense distància, cost, etc.

Si $W$ és una matriu de tamany $n\times n$ que conté els pesos de les arestes d'una gràfica, llavors $W^k$ (usant este producte de distància) dona les distàncies entre vèrtiços usant camins de llongitut ce a lo més $k$ arestes, i $W^n$ és la matriu de distàncies de la gràfica.

Una gràfica arbitrària $G$ sobre $n$ vèrtiços pot ser modelada com una gràfica completa ponderada sobre $n$ vèrtiços, assignant un pes d'un a cada aresta de la gràfica completa que correspon a una aresta de $G$ i zero a tots les arestes restants. Per a esta gràfica completa, $W$ és la matriu de adyacencia de $G$. La matriu de distàncies de $G$ es pot calcular a partir de $W$ com s'indica anteriorment, no obstant, $W^n$ calculada per la multiplicació matricial habitual solament codifica el número de camins entre dos vèrtiços de llongitut exactament $n$.

Matriu de distàncies mètriques

En moltes aplicacions, el valor d'una matriu de distàncies està en com pot codificar els axioma mètrics i en com es presta a l'us de tècniques d'àlgebra llineal. És dir, si $M=(x_{ij})$ en $1\le i,j\le N$ és una matriu de distàncies en una distància mètrica, llavors

1. Les entrades en la diagonal són totes zero, i.i. $x_{ii}=0$ para tot $1\le i\le N$.
2. Totes les entrades fòra de la diagonal són positives ($x_{ij}>0$ si $i\ne j$), és dir, és una matriu no-negativa.

1. La matriu és una matriu simètrica ($x_{ij}=x_{ji}$) i
2. Per a qualsevol $i$ i $j$, $x_{ij}\le x_{ik}+x_{kj}$ para tot $k$ (desigualtat del triàngul).

Una matriu de distàncies mètriques que pot ser encaixada en espai Euclidiano es diu una matriu de distàncies Euclidiana.

Un atre eixemple comú d'una matriu de distàncies mètriques sorgix en la teoria de còdics quan en un bloc de còdics els elements són cadenes de llongitut fixa sobre un alfabet i la distància entre ells està donada per la distancia Hamming. L'entrada més chicoteta distinta de zero, medix la capacitat de correcció i detecció d'errors del còdic.