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 S_E un pseudografo etiquetado y v un vértice de S_E, llamaremos peso de v en S_E a la suma del valor de las etiquetas de las aristas de S_E 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 :

EJEMPLO 1

Las matrices

\(\left( \begin{array}{cc} a & b \\ b & c \\ \end{array} \right)\quad; \quad\left( \begin{array}{ccc} a & b & c \\ b & d & f \\ c & f & g \\ \end{array} \right) \) tienen como grafos respectivos asociados los de la figura adjunta

valores 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) :

\(B_{T_E}= P·A_{S_E}·P^T\) siendo \(A_{S_E} \; y \;B_{T_E} \) y las matrices de adyacencia de los pseudografos etiquetados S_E y T_E 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) :

\( \left( \begin{array}{cccccc} \Sigma_{11} & \cdots & \Sigma^T_{h1} & K^T_{h+1,1} & \cdots & K^T_{h+r,1} \\ . & \cdots & . & . & \cdots & . \\ \Sigma_{h1} & \cdots & \Sigma_{hh} & K^T_{h+1,h} & \cdots& K^T_{h+r,h} \\ K_{h+1,1} & \cdots & K_{h+1,h} & A_{h+1,h+1} & \cdots& A^T_{h+r,h+r} \\ . & \cdots & . & . & \cdots & . \\ K_{h+r,1} & \cdots & K_{h+r,h} & A_{h+r,h+1} & \cdots & A_{h+r,h+r}\\ \end{array} \right)\) donde las \(\Sigma_{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 \(K_{hs} \) matrices de dimensión 1xp con todos sus elementos iguales, y las \(A_{pq} \) 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) :

\(\left( \begin{array}{ccccccc} q & 0 & \cdots & 0 & a_{1,p+1} & \cdots & a_{1,n} \\ 0 & q & \cdots & 0 & a_{1,p+1} & \cdots & a_{1,n} \\ 0 & 0 & \cdots & & & \cdots & \\ 0 & 0 & \cdots & q & a_{1,p+1} & \cdots & a_{1,n} \\ a_{1,p+1} & a_{1,p+1} & \cdots & a_{1,p+1} & b_{1+1,p+1} & \cdots & \\ & & \cdots & & & & \cdots \\ a_{1,n} & a_{1,n} & \cdots & & & \cdots & b_{n,n} \\ \end{array} \right)\) 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

\(\left( \begin{array}{cccccccc} q & 0 & 0 & a & b & c & d & 0 \\ 0 & q & 0 & a & b & c & d & 0 \\ 0 & 0 & q & a & b & c & d & 0 \\ a & a & a & p & 0 & 0 & 0 & 0 \\ b & b & b & 0 & p & 0 & 0 & 0 \\ c & c & c & 0 & 0 & r & 0 & f \\ d & d & d & 0 & 0 & 0 & r & g \\ 0 & 0 & 0 & 0 & 0 & f & g & s \\ \end{array} \right)\) de la que podemos obtener el valor propio doble q y la matriz propia :

\(\left( \begin{array}{cccccc} q & 3a & 3b & 3c & 3d & 0 \\ a & p & 0 & 0 & 0 & 0 \\ b & 0 & p & 0 & 0 & 0 \\ c & 0 & 0 & r & 0 & f \\ d & 0 & 0 & 0 & r & g \\ 0 & 0 & 0 & f & g & s \\ \end{array} \right)\) 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 :

\(\left( \begin{array}{cccccc} a & p & r & 0 & r & q \\ p & b & q & 0 & 0 & 0 \\ r & q & a & p & r & 0 \\ c & 0 & p & b & q & 0 \\ r & 0 & r & q & a & p \\ q & 0 & 0 & 0 & p & b \\ \end{array} \right)\qquad\qquad\qquad \left( \begin{array}{cccccc} a & r & r & p & 0 & q \\ r & a & r & q & p & 0 \\ r & r & a & 0 & q & p \\ p & q & 0 & b & 0 & 0 \\ 0 & p & q & 0 & b & 0 \\ q & 0 & p & 0 & 0 & b \\ \end{array} \right)\) 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)].

\(\left( \begin{array}{cccccccccc} 0 & c & 0 & 0 & 0 & 0 & 0 & 0 & b & 0 \\ c & 0 & b & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & b & 0 & b & 0 & 0 & 0 & 0 & 0 & a \\ 0 & 0 & b & 0 & c & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & c & 0 & b & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & b & 0 & b & 0 & 0 & a \\ 0 & 0 & 0 & 0 & 0 & b & 0 & c & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & c & 0 & b & 0 \\ b & 0 & 0 & 0 & 0 & 0 & 0 & b & 0 & a \\ 0 & 0 & a & 0 & 0 & a & 0 & 0 & a & 0 \\ \end{array} \right) \) 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

\(\left( \begin{array}{cccccccccc} 0 & 0 & 0 & c & 0 & 0 & 0 & 0 & b & 0 \\ 0 & 0 & 0 & 0 & c & 0 & b & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & c & 0 & b & 0 & a \\ c & 0 & 0 & 0 & 0 & 0 & b & 0 & 0 & 0 \\ 0 & c & 0 & 0 & 0 & 0 & 0 & b & 0 & 0 \\ 0 & 0 & c & 0 & 0 & 0 & 0 & 0 & b & 0 \\ 0 & b & 0 & b & 0 & 0 & 0 & 0 & 0 & a \\ 0 & 0 & b & 0 & b & 0 & 0 & 0 & 0 & a \\ b & 0 & 0 & 0 & 0 & b & 0 & 0 & 0 & a \\ 0 & 0 & 0 & 0 & 0 & 0 & a & a & a & 0 \\ \end{array} \right) \) Y teniendo en cuenta [3]

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

\(\left( \begin{array}{ccc} c & 2b & 0 \\ b & 0 & 3a \\ 0 & a & 0 \\ \end{array} \right) \quad ; \quad -c \) Si aplicamos la permutación [(1,2),(9,3),(8,4),(7,5), (10),(6)] tenemos :

\(\left( \begin{array}{cccccccccc} 0 & c & b & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ c & 0 & 0 & b & 0 & 0 & 0 & 0 & 0 & 0 \\ b & 0 & 0 & 0 & b & 0 & 0 & 0 & a & 0 \\ 0 & b & 0 & 0 & 0 & b & 0 & 0 & a & 0 \\ 0 & 0 & b & 0 & 0 & 0 & c & 0 & 0 & 0 \\ 0 & 0 & 0 & b & 0 & 0 & 0 & c & 0 & 0 \\ 0 & 0 & 0 & 0 & c & 0 & 0 & 0 & 0 & b \\ 0 & 0 & 0 & 0 & 0 & c & 0 & 0 & 0 & b \\ 0 & 0 & a & a & 0 & 0 & 0 & 0 & 0 & a \\ 0 & 0 & 0 & 0 & 0 & 0 & b & b & a & 0 \\ \end{array} \right) \) de donde resulta :

\(\left( \begin{array}{cccc} -c & b & 0 & 0 \\ b & 0 & b & 0 \\ 0 & b & 0 & c \\ 0 & 0 & c & 0 \\ \end{array} \right) \qquad\qquad \left( \begin{array}{cccccc} c & b & c & 0 & 0 & 0 \\ b & 0 & b & 0 & 2a & 0 \\ 0 & b & 0 & c & 0 & 0 \\ 0 & 0 & c & 0 & 0 & 2b \\ 0 & a & 0 & 0 & 0 & a \\ 0 & 0 & 0 & b & a & 0 \\ \end{array} \right)\) 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.

Estás en > Matemáticas y Poesía > Matemáticas
MONOGRAFIAS MATEMÁTICAS ~ ANÁLISIS NUMÉRICO
VALORES PROPIOS EN GRAFOS

VALORES PROPIOS EN GRAFOS

VALORES PROPIOS DE GRAFOS