Usted está aquí: Inicio / Actividades / Seminarios / Seminario Preguntón de Matemáticas Discretas / Actividades / Inconexión acíclica y feedback arc sets en gráficas planas

Inconexión acíclica y feedback arc sets en gráficas planas

Ponente: César Hernández
Institución: Facultad de Ciencias, UNAM
Tipo de Evento: Investigación
Cuándo 06/10/2015
de 17:00 a 18:00
Dónde Unidad Multidisciplinaria de Docencia e Investigación (UMDI), Aula 1. UNAM Campus Juriquilla, Querétaro
Agregar evento al calendario vCal
iCal
La inconexión acíclica de una gráfica se define como el máximo número de colores con los que una digráfica puede ser coloreada de tal forma que ningún ciclo dirigido esté propiamente coloreado. Un feedback arc set en la digráfica D es un conjunto de flechas S tal que D-S es una digráfica acíclica.

Una manera usual de estudiar un parámetro para digráficas en gráficas no dirigidas, es considerar el valor máximo (o mínimo) de dicho parámetro sobre todas las posibles orientaciones de una gráfica. Por ejemplo, podemos definir la inconexión acíclica de una gráfica G como el mínimo de las inconexiones acíclicas tomado sobre todas las posibles orientaciones de G; análogamente, decimos que la cardinalidad de un feedback arc set mínimo para una gráfica G es el máximo, sobre todas las posibles orientaciones de G, de las cardinalidades de los feedback arc set mínimos.

En esta plática relacionaremos ambos parámetros para algunas familias de gráficas planas.