Algunos ejemplos de algoritmos certificadores en gráficas

Ponente: César Hernández Cruz
Institución: Facultad de Ciencias UNAM
Tipo de Evento: Investigación, Divulgación

Cuándo	13/02/2024 de 12:00 a 13:00
Dónde	Auditorio "Alfonso Nápoles Gándara"
Agregar evento al calendario	vCal iCal

Es común implementar algoritmos que resuelven problemas de decisión, es decir, problemas

que responden una pregunta cuya respuesta es sí o no. Por ejemplo, es fácil implementar un

algoritmo que reciba como entrada dos enteros positivos, y determine si éstos son primos

relativos. Dicho algoritmo podría simplemente responder "sí" o "no", dada una entrada $(x,y)$,

sin embargo, si tuviéramos dudas sobre la correcta implementación del algoritmo, no tendríamos

información adicional para determinar si la respuesta es correcta o no, lo que nos orillaría a

ejecutar un segundo algoritmo que resuelva el mismo problema para "verificar" la respuesta.

Si adicionalmente a la respuesta "sí", el algoritmo devolviera los coeficientes de una combinación

lineal de $x$ y $y$ igual a $1$, y adicionalmente a la respuesta "no", el algoritmo devolviera un

divisor común de $x$ y $y$ mayor a $1$, entonces sería fácil verificar si una respuesta del

algoritmo es correcta, sin necesidad de ejecutar otro algoritmo que resuelva el mismo problema.

A esta información adicional que nos ayuda a verificar la correcta implementación de un algoritmo

se le llama "certificado", y un algoritmo que devuelve certificados para ambos tipos de respuesta

(sí o no), se le conoce como certificador.

En teoría de gráficas, usualmente se buscan algoritmos para determinar si una gráfica tiene o

no alguna propiedad. Es deseable que dichos algoritmos sean certificadores, pero no siempre

resulta claro qué debe usarse como certificado. En esta plática presentaremos caracterizaciones

para algunas propiedades de gráficas que dan lugar a certificados naturales que pueden ser

utilizados en algoritmos para su reconocimiento. En muchos casos, la naturaleza constructiva

de las demostraciones induce de forma natural un algoritmo certificador que resulta eficiente

y fácil de implementar.