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
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.
