Supongamos que queremos localizar un intruso en una red a partir de detectores colocados en algunos de sus nodos. Para este propósito se pueden utilizar los conjuntos dominantes y los conjuntos resolutivos de un grafo.
Los conjuntos dominantes fueron introducidos hace casi 60 años con otro nombre por Berge, y unos años más tarde Ore ya utilizó el nombre actual. Pero mucho antes, a mediados del siglo XIX, los jugadores de ajedrez se habían planteado problemas equivalentes a encontrar conjuntos dominantes. Probablemente el más conocido consiste en determinar cuál es el mínimo número de reinas que hay que colocar en un tablero de ajedrez para que todas las casillas estén o bien ocupadas o bien atacadas por una reina.
Los conjuntos resolutivos fueron introducidos de forma independiente por Slater y por Harary y Melter a mediados de los años 70. En cierto modo equivalen a un sistema de referencia en un grafo utilizando la distancia entre vértices. El cardinal mínimo de un conjunto resolutivo es la dimensión métrica.
Desde entonces son muchos los trabajos publicados que tratan estos dos conceptos y multitud de variantes de los mismos. En esta charla repasaremos algunas de sus propiedades y aplicaciones.
Fecha y hora: viernes 29 de julio a las 9:00.
Lugar: Auditori de l’edifici Vèrtex, Universitat Politècnica de Catalunya.