Ingenier #$&%: Matriz de adyacencia

Namor

Dado un grafo etiquetado G = {V, E, L, I} tal que |V| = n y una permutación de los vértices en V = { v0, v1,…, vn-1}, la matriz de adyacencia de G respecto a dicha permutación es X = (xij)ij ^n-1 donde:

El código de G usando X ha sido definido de varias maneras. En adelante, explicaremos dos maneras de construir este código. La primera variante ubica las etiquetas de los vértices y luego adiciona las filas de la sub matriz estrictamente triangular inferior(la matriz triangular inferior excluyendo la diagonal).

Un mismo grafo puede tener varias matrices de adyacencias ya que existe una dependencia con el orden de los vértices que se utilizo durante la construcción de la matriz. Caracterizar un grafo etiquetado requiere de una representación que sea única en dicho grafo y en todos aquellos que son isomorfos con este. Es por eso que se define la matriz de adyacencia canónica a partir del código de la matriz.