Resúmenes de las conferencias:
"Conectividad algebraica y fórmula de Rice"
Federico Dalmao
La conectividad algebraica o número de Fiedler de un grafo es el segundo menor valor propio de su matriz laplaciana. Esta conectada con varios invariantes del grafo y la propuesta es que esta característica es una buena medida de cuán conexo es el grafo. La expresión del número de Fiedler como mínimo de una forma cuadrática motiva el uso de la fórmula de Rice en este problema.
"Grafos de asociaciones en modelos de memorias neurales "
Andrés Pomi (Biofisica-FCIEN)
Los vínculos entre la teoría de grafos y la neurociencia cognitiva, se habían restringido a dos territorios temáticos separados. Por un lado estudios clásicos en el campo de la psicología representando los vínculos entre palabras o conceptos mediante los llamados grafos semánticos, y por otro lado, algunos estudios más recientes que empleaban grafos para caracterizar la conectividad neural, anatómica, en los sistemas nerviosos. Los enfoques de redes complejas enfatizaron, a partir de los años noventa, el carácter que las redes conceptuales compartían con otras redes complejas naturales y artificiales, pero nada se sabía sobre cómo nuestro sistema nervioso podía sustentar dichas redes cognitivas. Nuestro trabajo vino a llenar este vacío mostrando que de los modelos de memorias asociativas surgen naturalmente grafos de las asociaciones guardadas en las memorias, y que estos grafos y su espectro son invariantes con respecto al código neural. En esta presentación mostraremos dichos grafos de asociaciones, sus características, el vínculo de las memorias con la matriz de adyacencia del grafo y su espectro, y extensiones de este desarrollo para el caso de modelos de memorias que permiten asociaciones adaptativas. Se enfatizarán los horizontes que abre esta nueva perspectiva.
"Sincronizabilidad de los grafos circulantes."
Eduardo Canale - Pablo Monzón
A todo grafo $G$ le asociamos una función de energía $U(x)$ tal que el sistema $dot x = U' (x)$ modela el comportamiento de osciladores débilmente acoplados según $G$ de acuerdo con el modelo de Kuramoto.
A los puntos estacionarios de $U$ les llamamos equilibrios de $G$. La matriz Hessiana $U''$ de $U$ en dichos equilibrios comparte muchas de las propiedades de la matriz Laplaciana de $G$. En particuar si el equilibrio es un consenso $x=(c,c,...,c)$ entonces $U''(x)$ es exactamente la Laplaciana de $G$. Al igual que para la Laplaciana definimos el número de Fiedler de $G$ en $x$ como el menor valor propio de $U''(x)$ en $(1,1,...,1)^T$. Ahora dicho número puede ser negativo, cero o positivo. Si dicho número es negativo para todo $x$ de equilibrio que no sea un consenso, entonces el grafo es sincronizante, en el sentido de que con medida positiva toda órbita de $dot x = U'(x)$ tenderá a un consenso.
En esta charla comentaremos algunos resultados respecto a esos números de Fiedler para los grafos circulantes, que son aquellos cuya matriz de adyacencia es circulante.
"Caracterización de soluciones óptimas 2-conexas sobre grafos con desigualdad triangular en costos".
Franco Robledo
"En el diseño de redes de fibra óptica de área metropolitana, las topologías 2-conexas (tanto 2-arista-conexas como 2-nodo-conexas) juegan un rol preponderante.
Niveles superiores de conectividad entre nodos, usualmente no son requeridos salvo aplicaciones de redundancia sobreexigida, típicamente en requisitos militarares.
Dado un conjunto de nodos V y los costos de conexión entre ellos (e.g. modelando el costo de dragado y puesta en operación de la línea); bajo hipótesis de desigualdad triangular de los costos de conexión entre nodos de la red a diseñar, se conocen resultados que caracterizan las topologías óptimas 2-conexas que cubren los nodos V.
Veremos además, la relación existente entre el ciclo hamiltoniano de costo mínimo que cubre V respecto del cósto óptimo de la subred 2-conexa que cubre V. Dicha relación es rígida y no supera el valor 4/3 para cualquier red bajo hipótesis de desigualdad triangular de costos de conexión. Este resultado es de altísima relevancia en el contexto de planificación de redes de alto porte con estructura anillada."
"Modelos de confiabilidad eAn grafos con restricciones de diametro"
Héctor Cancela
El modelo de confiablidad clásico en grafos supone nodos perfectos y aristas que pueden fallar de forma independiente con cierta probabilidad, y toma como critero de funcionamiento de un grafo el que existan caminos que conecten sus nodos terminales.
El modelo de confiabilidad "diámetro acotada" exige además que la conexión sea posible a través de caminos de distancia menor o igual a una cota superior dada, lo que en el caso "todos terminales" corresponde a acotar el diámetro del grafo cuyas aristas son aquellas en funcionamiento del grafo original.
En esta presentación, veremos este modelo y algunas de sus propiedades, en particular referidas a la posibilidad de calcular eficientemente la confiabilidad, sea de manera exacta o aproximada.
