Título
Número acromático de gráficas gramíneas bipartitas
Autor
ERNESTO CASTELAN CHAVEZ
Colaborador
RAFAEL LOPEZ BRACHO (Asesor de tesis)
LAURA ELENA CHAVEZ LOMELI (Asesor de tesis)
Nivel de Acceso
Acceso Abierto
Materias
Coloración de gráfos; Biología computacional. Bipartite graphs. - (LCSH) Gráfos bipartidos. - (DGBUNAM) Acoplamiento en gráficas. - (DGBUNAM) Optimización combinatoria. - (DGBUNAM) QA166.14 - (LCC) INGENIERÍA Y TECNOLOGÍA - (CTI) CIENCIAS TECNOLÓGICAS - (CTI) TECNOLOGÍA DE LOS ORDENADORES - (CTI) HEURÍSTICA - (CTI)
Resumen o descripción
44 páginas. Maestría en Optimización.
En este trabajo estudiamos diversas propiedades de las gráficas gramíneas bipartitas, enfocándonos en particular en las coloraciones completas y el número acromático de las mismas. En el capítulo 1, presentamos al lector los conceptos preliminares más importantes para el desarrollo de éste trabajo. En el capíutlo 2, introducimos una clasificación de las gramíneas bipartitas en varias familias, y presentamos varias propiedades relacionadas con la estructura de estas familias, en particular, mostramos dos resultados importantes: una caracterización de un grupo de gramíneas bipartitas en términos de acoplamientos y la relación que el mismo grupo guarda con la familia de torneos regulares. También exploramos el problema de reconocer gráficas gramíneas en estas familias y presentamos un programa entero y un algoritmo que resuelven el problema. En cuanto a problemas de coloración, en el capítulo 3, damos una cota superior, que es justa, para el número acromático de una familia de gramíneas bipartitas y clasificamos las coloraciones completas que alcanzan dicha cota. Estudiamos algunas de las coloraciones completas mencionadas y exhibimos condiciones necesarias y condiciones suficientes para la existencia de estas coloraciones. Así mismo, presentamos técnicas para obtener y extender coloraciones completas en las gráficas de interés.
Editor
Universidad Autónoma Metropolitana (México). Unidad Azcapotzalco. Coordinación de Servicios de Información.
Fecha de publicación
16 de marzo de 2016
Tipo de publicación
Tesis de maestría
Recurso de información
Formato
application/pdf
Idioma
Español
Audiencia
Estudiantes
Investigadores
Repositorio Orígen
Repositorio Institucional Zaloamati
Descargas
60