Estás en > Matemáticas y Poesía > Matemáticas

MONOGRAFIAS MATEMÁTICAS
ANÁLISIS NUMÉRICO

VALORES PROPIOS EN GRAFOS

 

VALORES PROPIOS DE GRAFOS

DEFINICIONES

Llamamos pseudografo [1] a la terna S = (V, E, θ) compuesta de un conjunto no vacío V (cuyos elementos denominamos vértices) un conjunto E de aristas y la función θ que a cada arista α ∈ E le asocia un par no ordenado de vértices (v,w) = (w,v), no necesariamente distintos, llamados extremos de dicha arista.

Sea S un pseudografo y v un vértice de S, llamamos grado de v en S al número de aristas de S que tienen al vértice v por extremo

Un pseudografo es regular si todos sus vértices tienen el mismo grado.

Un pseudografo S está etiquetado si sus aristas tienen asignado un número.

Toda matriz simétrica puede tomarse como la matriz de adyacencia [2] de un pseudografo etiquetado.

Sea SE un pseudografo etiquetado y v un vértice de SE, llamaremos peso de v en SE a la suma del valor de las etiquetas de las aristas de SE que tienen el vértice v por extremo.

Un pseudografo está ponderado si todos sus vértices tienen el mismo peso. Si dicho peso es q, el pseudografo será q-ponderado.

Dos vértices son simétricos respecto de un elemento de simetría, si mediante una operación de simetría centrada en el elemento considerado son indistinguibles uno de otro.

Un pseudografo etiquetado se dice que es r-partido si todos sus vértices se pueden agrupar en r conjuntos tales que los elementos de cada uno de dichos conjuntos cumplen :

    i ) No son adyacentes entre si
    ii) Tienen las mismas adyacencias
EJEMPLO 1

Las matrices
valores propios de grafos
tienen como grafos respectivos asociados los de la figura adjunta

valores propios de grafosvalores propios de grafos
TEOREMA 1

La matriz de adyacencia de un pseudografo q-ponderado tiene al menos un valor propio igual a q.

Demostración

De las definiciones anteriores se deduce fácilmente que la suma de los elementos de la fila (columna) i-ésima de la matriz de adyacencia da el peso del vértice i-ésimo del pseudografo asociado.
Cuando decimos que el pseudografo está q-ponderado, estamos diciendo que todas las filas (columnas) de la matriz de adyacencia suman el valor q; por lo tanto, considerando [3] queda demostrado lo que nos proponíamos.

TEOREMA 2

Todo pseudografo etiquetado isomorfo a otro que posea algún elemento de simetría, tiene una matriz sigma-reducible [4]

Demostracion

Las matrices de adyacencia de dos pseudografos etiquetados isomorfos están relacionadas por una ecuación de la forma (1) :
valores propios de grafos
siendo valores propios de grafos y las matrices de adyacencia de los pseudografos etiquetados SE y TE respectivamente, y P la matriz de permutación asociada a la biyección f del conjunto {1,...,n} en si mismo. Por lo tanto, según la definición 5 de [3], si una matriz es sigma-reducible también lo será cualquier otra relacionada con ella por una ecuación como (1)
deberemos ver entonces si la matriz de adyacencia de un pseudografo etiquetado que posea algún elemento de simetría es sigma-reducible. Para ello, nos basta con permutar sus filas y columnas de modo que los correspondientes a los vértices indistinguibles bajo la operación de simetría asociada al elemento de simetría referido estén juntas, con lo que resulta una matriz de la forma (2) :

valores propios de grafos

donde las Σij son matrices sigma de dimensión mxm (siendo m el número de vértices indistinguibles bajo la operación de simetría), las Khs matrices de dimensión 1xp con todos sus elementos iguales, y las Apq son matrices cualesquiera.
El número de filas desde h+1 hasta h+r depende del número de vértices no agrupables para la operación de simetría aplicada o, lo que es igual, al número de vértices contenidos en el elemento de simetría.
La matriz dada en (2) cumple las hipótesis del corolario al teorema 1de [3] con lo que se demuestra lo que nos proponíamos.

EJEMPLO 2

El grafo K3,3 (fig adjunta) es bi-partido.

valores propios de grafos

TEOREMA 3

Todo pseudografo etiquetado r-partido que tenga alguno de sus conjuntos con todos sus elementos simétricos, tiene una matriz de adyacencia sigma-reducible.

Demostración

Permutamos las filas y columnas de la matriz de adyacencia de modo que las p primeras sean las correspondientes a los p vértices del conjunto con todos sus elementos simétricos. En esas condiciones, la matriz resultante será de la forma (3) :

valores propios de grafos

que es claramente sigma-reducible.

EJEMPLO 3

valores propios de grafos

El pseudografo etiquetado adjunto es tetrapartido y su matriz de adyacencia puede escribirse como la representada

valores propios de grafos
de la que podemos obtener el valor propio doble q y la matriz propia :

valores propios de grafos

EJEMPLO 4

valores propios de grafos

Para el grafo de este ejemplo, el elemento de simetría es un eje perpendicular al plano que contiene los vértices. La matriz de adyacencia y su transformada mediante la permutación (1,3,5,2,4,6) vienen dadas por :
valores propios de grafos
Donde la matriz de la derecha es sigma-reducible

EJEMPLO 5

valores propios de grafos
Los ejes de simetría de la figura permiten las permutaciones : [(1,2),(9,3),(8,4),(7,5), (10),(6)] ; [(1,4,7),(2,5,8)(3,6,9),(10)].

valores propios de grafos
Si la matriz de adyacencia del grafo es la representada por la matriz adjunta, aplicando la permutación [(1,4,7),(2,5,8)(3,6,9),(10)] resulta

valores propios de grafos
Y teniendo en cuenta [3]

valores propios de grafos
A su vez, la primera de las matrices se descompone en :

valores propios de grafos
Si aplicamos la permutación [(1,2),(9,3),(8,4),(7,5), (10),(6)] tenemos :

valores propios de grafos
de donde resulta :
valores propios de grafos
BIBLIOGRAFIA

1. E. Bujalance, J.A. Bujalance, A.F. Costa, E. Martinez; Elementos de Matemática Discreta. Ed Sanz y Torres.
2. K. Rivnikov; Análisis Combinatorio. Ed Mir.
3. Matrices sigma, J. A. Hervás.
4. Matrices Sigma-reducibles, J. A. Hervás.
 

OTROS CONTENIDOS EN EL SITIO MATEMÁTICAS Y POESÍA

┐Te ha sido de utilidad este artículo sobre valores propios en grafos?.- íRecomiénda esta página!

Otros usuarios de Matemáticas y poesía también han visto:

Ejercicios resueltos

Trabajos Arquitectura

El tesoro mágico

Poesía y emoción

Mis Repoelas


tema escrito por: José Antonio Hervás