El próximo jueves, 12 de noviembre, tendrá lugar el Colloquium-IMUEx, impartido por el Dr. D. Carlos Marijuán López IMUVa, Universidad de Valladolid), titulado «Cómo mirar la estructura de un digrafo». El colloquium se celebrará en el aula 208 del Aulario de la Facultad de Ciencias a las 16:00.

Resumen: En esta charla proponemos una visión estructural de las redes dirigidas. Partimos de ejemplos de redes de comunicación y de los problemas clásicos de Euler y Hamilton para una breve introducción a la teoría de grafos de la que presentamos sus propiedades más relevantes para una primera clasificación. Introducimos conceptos muy básicos en digrafos (grafos dirigidos) para precisar el concepto de conexión fuerte y su representación matricial. La idea central consiste en descomponer cualquier digrafo en componentes fuertemente conexas cuya condensación es acíclica. Su estudio combina así la estructura de orden entre componentes con la estructura cíclica dentro de ellas.

Para los digrafos acíclicos se describe la organización de sus vértices por niveles y su ordenación natural. Para los fuertemente conexos (FC) se introducen los minimales (FCM), que pierden esta propiedad al eliminar cualquier arco. Se presenta una caracterización constructiva recursiva de los digrafos FCM mediante ampliaciones internas y externas, junto con resultados enumerativos y procesos algorítmicos.