Aspectos Algorítmicos de las Estructuras Aritméticas

Ponente(s): Ralihe Raúl Villagrán Olivas, Dr. Carlos E. Valencia Oleta
Sea $G=(V,E)$ una gráfica. La matriz $L(G)=\textrm{Diag}(deg_G)-A(G)$ es llamada matriz Laplaciana de $G$. Una estructura aritmética de $G$ es un par de vectores $(d,r)$ tales que $L_d(G)r^t=0^t$ donde $L_d(G)=\textrm{Diag}(d)-A(G)$ es la pseudo-Laplaciana de $G$. Observemos que $(deg_G,1)$ siempre es una estructura aritmética de $G$. Las estructuras aritméticas de gráficas fueron introducidas por D. Lorenzini en 1989 y recientemente fueron estudiadas para matrices enteras no-negativas. En ambos casos se obtuvieron resultados de finitud para el conjunto de estructuras aritméticas, por lo tanto una pregunta natural es ¿existe un algoritmo que compute todas las estructuras aritméticas de una matriz entera cuadrada no negativa $A$?. En esta charla exploraremos la teoría necesaria para responder esta pregunta y presentaremos dicho algoritmo.