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