Un grafo describe quién está conectado con quién. Al convertirlo en una matriz podemos estudiar cómo se difunden valores, detectar componentes y buscar separaciones. Construiremos la matriz de un camino pequeño y comprobaremos cada propiedad con sus tres vértices antes de usar el resultado general.
Si necesitas repasar:
1. La matriz de adyacencia registra aristas y el laplaciano compara vecinos
Fijamos un grafo finito simple no dirigido, sin bucles. 
vale uno si i y j están unidos y cero si no. La suma de la fila i es el grado 
. D pone los grados en la diagonal y L=D−A es el laplaciano no normalizado.
L es simétrico y sus filas suman cero.
.El vector x asigna un valor a cada vértice; Lx suma cuánto difiere de sus vecinos.
Construir el camino 1−2−3
Hay dos aristas: {1,2} y {2,3}.
Grados
Uno, dos y uno.
Adyacencia
.Laplaciano
.
Las filas comparan cada valor con los de los vértices realmente conectados.
No se añade una arista entre uno y tres por estar en la misma componente.
Una constante no produce diferencias
x=(5,5,5) en ese camino.
Primera fila
5−5=0.Central
−5+10−5=0.Última
−5+5=0.
Lx=0 aunque el grafo sí tenga aristas.
La matriz mide diferencias de valores, no si el dibujo está vacío.
2. La energía es una suma de cuadrados, una vez por arista
²+
²−2x_ix_j=(−)².
.El grafo es no dirigido y cada arista se cuenta una sola vez en esta suma.
La simetría y no negatividad hacen L semidefinida positiva: todos sus autovalores son reales y no negativos. La energía es baja si los vecinos tienen valores parecidos. Sumar una misma constante a todos los valores no la cambia.
Calcular energía por dos caminos
x=(1,2,4) en el camino de tres vértices.
Aristas
(1−2)²+(2−4)²=1+4=5.Matriz
Lx=(−1,−1,2).Producto
xᵀLx=−1−2+8=5.
Las dos cuentas deben coincidir.
Los valores uno, dos y cuatro son componentes de x, no grados.
Trasladar no cambia diferencias
Pasamos de x=(1,2,4) a y=(11,12,14).
Diferencias
11−12=−1 y 12−14=−2.Energía
Vuelve a ser uno más cuatro.
Razón
L1=0 y las diferencias eliminan la constante diez.
El origen elegido para los valores no altera la energía.
Multiplicar todos los valores por c sí la multiplica por c².
3. El núcleo permite contar componentes conexas
Si Lx=0, xᵀLx=0 y cada cuadrado de la suma anterior tiene que ser cero.
=.Al seguir caminos, el valor se mantiene constante en toda componente.
Se puede elegir una constante independiente para cada componente. Así la dimensión del núcleo y la multiplicidad del autovalor cero son el número de componentes conexas. Los aislados también cuentan.
Dos componentes, dos constantes libres
Grafo con aristas {1,2} y {3,4}.
Primera
El núcleo exige x₁=x₂.Segunda
Exige x₃=x₄.Familia
x=(a,a,b,b), con a y b libres: dimensión dos.
El cero aparece dos veces en el espectro.
No hay obligación de que a=b, porque ningún camino une las componentes.
Un aislado añade otra dirección nula
Camino 1−2−3 y un vértice cuatro aislado.
Camino
Sus valores nulos por L son (a,a,a).
Aislado
Su fila es cero y su valor b es libre.
Núcleo
(a,a,a,b), dimensión dos.
Un aislado es una componente completa de un solo vértice.
Se trata aparte cuando después se divida por grados.
4. La traza comprueba un espectro, pero no lo determina
=2m.Cada arista aporta uno al grado de cada extremo. Hay n autovalores si hay n vértices, aunque el número de aristas sea distinto.
Contar ceros y sumar autovalores verifica condiciones necesarias de una lista propuesta. No basta para demostrar que esa lista sea correcta. Incluso conocer el espectro completo no identifica siempre un grafo hasta isomorfismo.
Comprobar el espectro del camino
Para 1−2−3 se proponen 0,1,3.
Cantidad
Son tres, como los vértices.
Suma
Cero más uno más tres es cuatro, igual a 2·2 aristas.
Ceros
Hay uno, compatible con que el grafo sea conexo; falta aún comprobar los vectores propios.
La lista supera estas comprobaciones básicas.
No se deduce su validez solo por sumar cuatro.
Los mismos grados totales no fijan los autovalores
Un camino y una estrella, ambos con cuatro vértices y tres aristas.
Traza
Ambos tienen traza seis.
Conexión
Ambos tienen un único autovalor cero.
Espectros
La estrella tiene 0,1,1,4; el camino 0,2−√2,2,2+√2.
Dos invariantes iguales no bastan para identificar la distribución espectral.
El ejemplo muestra esa insuficiencia, no cospectralidad entre estos dos grafos.
5. El segundo autovalor excluye la dirección constante para medir conectividad
En el caso conexo, y también con la multiplicidad pertinente si no lo es, 
.
Excluir constantes elimina una dirección de energía cero que siempre existe. Un vector casi constante dentro de dos grupos, pero diferente entre ellos, concentra energía en las aristas que los unen. Ese es el vínculo con buscar particiones, sin afirmar que el autovector dé siempre el corte óptimo.
Verificar un modo no constante
x=(1,0,−1) en el camino de tres vértices.
Centrar
Sus componentes suman cero.
Aplicar L
Lx=(1,0,−1)=x.Cociente
La energía y la norma cuadrada valen dos, de modo que el cociente es uno.
Es un vector propio de autovalor uno.
En este camino, junto con los otros dos modos, se verifica que es λ₂.
Una separación completa hace λ₂ cero
Dos componentes no vacías de tamaños r y s.
Valores
Asignamos s en la primera y −r en la segunda.
Ortogonalidad
La suma rs−sr es cero.
Energía
Dentro de cada componente no hay diferencias y entre ellas no hay aristas: energía cero.
Existe una dirección no constante con cociente cero.
Eso concuerda con multiplicidad del cero mayor que uno.
6. Normalizar por grados cambia el operador y el vector nulo
Sin vértices aislados, el laplaciano normalizado es 
. Sus autovalores están entre cero y dos. Su vector nulo natural es D¹ᐟ²1, con componentes √, que no suele ser constante.
I−D⁻¹A, asociado al paseo aleatorio, es similar a ℒ cuando D es invertible. L y ℒ tienen escalas distintas. Con grados cero hay que declarar una convención adicional; aquí los excluimos antes de usar inversas de D.
El camino normalizado
Grados uno, dos y uno.
Matriz
.Vector nulo
Multiplicar por (1,√2,1) da cero.
Contraste
Multiplicar por (1,1,1) no da cero.
La normalización cambia qué representa la dirección constante en las coordenadas transformadas.
El vector original constante se convierte en el vector de raíces de grados.
Un grafo regular permite comparar escalas
Todos los grados son d>0.
Diagonal
D=dI.Normalizar
ℒ=L/d.Espectro
Cada autovalor de ℒ es el correspondiente de L dividido por d.
En grafos regulares la relación es una escala uniforme.
Con grados distintos no se divide todo por un único grado.
7. Cheeger conecta un corte medido por volumen con el espectro normalizado
El volumen de S es la suma de sus grados. La conductancia φ es el mínimo de |∂S|/vol(S) entre conjuntos de volumen positivo no mayor que la mitad del volumen total.
La cota inferior se entiende centrando el indicador: y=1_S−a1 con a=vol(S)/vol(V).
La cota superior requiere además un argumento de umbrales del vector.
Calcular conductancia del camino pequeño
Camino 1−2−3; volumen total cuatro.
Conjuntos permitidos
Los de volumen positivo como máximo dos: una hoja, el centro o las dos hojas.
Cocientes
Una hoja: 1/1; centro: 2/2; dos hojas: 2/2.
Resultado
Todos dan uno: φ=1.El espectro normalizado 0,1,2 da 1/2≤1≤√2.
La desigualdad proporciona cotas, no necesariamente igualdad.
Se usa ν₂=1 del operador normalizado, no λ₂ de otro grafo o escala.
Un corte con pocas aristas relativo a su volumen
Un conjunto S tiene volumen diez, frontera dos y no supera la mitad del total.
Cociente
|∂S|/vol(S)=1/5.Mínimo
φ≤1/5 porque este S es un candidato.Espectro
ν₂/2≤φ implica ν₂≤2/5.
Un corte concreto da una cota superior para la conductancia mínima.
El denominador es volumen, no número de vértices.
8. Los modos propios muestran cómo se difunden los valores
En x′=−Lx, un vector propio v con autovalor λ evoluciona como exp(−λt)v. Como L es simétrica, sus vectores propios forman una base ortonormal tras elegirla adecuadamente. Los modos de autovalor positivo se amortiguan.
En una componente conexa, el modo constante permanece y los demás decaen. La media de los valores iniciales en esa componente se conserva. En un grafo no conexo cada componente conserva su propia media; no se mezclan valores sin aristas entre ellas.
Verificar los tres modos del camino
v₀=(1,1,1), v₁=(1,0,−1), v₃=(1,−2,1).
Productos
Lv₀=0, Lv₁=v₁ y Lv₃=3v₃.Independencia
Son ortogonales entre sí y no nulos.
Espectro
Completan las tres dimensiones y prueban la lista 0,1,3.
La comprobación de vectores completa lo que la traza sola no demostraba.
Los vectores dibujados aún no están normalizados a norma uno.
Una difusión con media conocida
x(0)=(3,2,1)=2v₀+v₁.
Evolución
x(t)=2v₀+exp(−t)v₁.Componentes
(2+exp(−t),2,2−exp(−t)).
Límite
Todas tienden a dos, la media inicial.
El modo constante fija el equilibrio y el otro describe la diferencia que desaparece.
La media permanece dos en todo instante.
9. Los certificados pequeños ayudan a usar el espectro sin confundir conclusiones
Se comprueban simetría, filas nulas, grados, energía, traza y ecuaciones Lv=λv. Para aproximaciones numéricas también se mide el residual y se tienen en cuenta multiplicidades: un autovector no es único si su autovalor es repetido.
Ordenar vértices por un vector propio y probar umbrales ayuda a encontrar cortes. Una garantía necesita relacionar el algoritmo, el cociente y la definición del corte. Un dibujo bonito o una lista de números no constituye por sí solo un certificado de optimalidad combinatoria.
Un autovector tiene libertad de signo
Lv=λv.
Multiplicar
L(−v)=−Lv.Reescribir
−λv=λ(−v).Interpretar
Cambiar todos los signos no cambia λ, aunque invierta el orden visual de los vértices.
La orientación global del vector no es una característica nueva del grafo.
Con multiplicidad también puede cambiar la base dentro del mismo espacio propio.
Comprobar un vector indicador
En el camino, S={1} y χ_S=(1,0,0).
Frontera
Solo sale la arista {1,2}.
Energía
χ_SᵀLχ_S=1.Identidad
Coincide con el número de aristas de frontera; para Rayleigh de λ₂ aún habría que centrar el vector.
El indicador conecta directamente una partición con una cuenta matricial.
No se usa un vector no centrado en una minimización que exige x⊥1.
Ahora lo resolvemos de principio a fin.
EJEMPLO RESUELTO 1
Camino de tres vértices
Escribe L para 1−2−3.
Leer aristas
El camino tiene {1,2} y {2,3}.
Grados
Son uno, dos y uno.
Construir D
.Construir A
.Restar
.Comprobar
Las tres filas suman cero y L es simétrica.
Ese es el laplaciano del camino.
Las tres filas suman cero.
EJEMPLO RESUELTO 2
Traza y aristas
Para un grafo con 6 aristas, calcula la suma de autovalores de L.
Leer el grafo
Tiene seis aristas.
Contar grados
Cada arista aporta dos a la suma de grados.
Total
Σ=2·6=12.Traza
La diagonal de L contiene los grados, luego tr(L)=12.Espectro
La suma de autovalores con multiplicidad es la traza: doce.
Alcance
No se necesita calcularlos uno a uno; la identidad no determina por sí sola cada autovalor.
La suma es 12.
No requiere calcular cada autovalor.
Los símbolos que hemos usado
- A
- Matriz de adyacencia, simétrica para un grafo simple no dirigido.
- D
- Matriz diagonal de grados.
- L=D−A
- Laplaciano combinatorio no normalizado.
- xᵀLx
- Energía de diferencias entre valores en vértices vecinos.
- λ₂
- Segundo autovalor ordenado de L para n≥2.
- ℒ
- Laplaciano normalizado, con una convención explícita.
- Cociente de Rayleigh
- xᵀLx dividido por xᵀx para x no nulo.
Ahora te toca a ti.
Tienes cinco ejercicios. Inténtalos; las pistas te ayudan si te atascas.
Practicar este tema →