Resultados: visualización detallada
Registro 1 de 1 para la búsqueda tipo de materia Tomografía discreta
Realizaciones Disjuntas de Secuencias de Grado en Grafos con Algunas Aplicaciones a Tomografía Discreta
Guíñez Abarzúa, Flavio Ricardo
Matamala Vásquez, Martín
Chrobak, Marek
Goles Chacc, Eric
Queyranne, Maurice
Rapaport Zimmermann, Iván
2009
- Datos de edición Programa Cybertesis
- Tipo de Documento Libro
-
Materia
Tomografía
Grafos bipartitos
Secuencias de grado
Np - difícil
Tomografía discreta -
Descripción
Esta tesis trata sobre un problema de reconstrucción en Tomografía Discreta en el cual se está interesado en colorear una grilla usando k colores, de tal forma que para cada fila y columna, el número de celdas de cada color sea un cierto valor previamente dado. Para k = 2, un resultado clásico de la Combinatoria entrega una condición necesaria y suficiente para la existencia de tal coloración junto con un algoritmo polinomial para const ...Esta tesis trata sobre un problema de reconstrucción en Tomografía Discreta en el cual se está interesado en colorear una grilla usando k colores, de tal forma que para cada fila y columna, el número de celdas de cada color sea un cierto valor previamente dado. Para k = 2, un resultado clásico de la Combinatoria entrega una condición necesaria y suficiente para la existencia de tal coloración junto con un algoritmo polinomial para construirla cuando existe. Por otro lado, Chrobak y Dürr mostraron que para k mayor o igual a 4 el problema es NP - difícil. La equivalencia natural entre una grilla y un grafo bipartito completo muestra que el caso k=3 corresponde a la restricción a esta clase de grafos del siguiente problema: Dados un grafo G y funciones enteras b¹ y b² en V(G), ¿existen b¹ y b² - factores de G que sean disjuntos? En esta tesis introducimos una nueva condición para este problema, la que resulta ser suficiente cuando G es un grafo bipartito completo y la diferencia entre el máximo y mínimo valor de b¹ + b² es a los más dos. La demostración de este resultado se basa en un algoritmo polinomial que encuentra dos factores disjuntos o bien un certificado de inexistencia. Junto con esto, la contribución principal de esta tesis es la prueba de NP - dificultad del problema para grafos bipartitos completos cuando no se impone ninguna condición a b¹ y b². Esto resuelve el caso k = 3 del mencionado problema en Tomografía Discreta, lo que cierra el problema para todos los valores de k. Como corolario obtenemos además que el problema para grafos completos es también NP - difícil. Para el problema de unicidad, caracterizamos las transformaciones que preservan las funciones b¹ y b² cuando G es un grafo bipartito. Este resultado es luego utilizado para probar la existencia de invariantes para algunas 3 - coloraciones de la grilla. Además, estudiamos la generalización del problema de k - coloración a la reconstrucción de embaldosados de la grilla usando como baldosas k rectángulos de diferentes tamaños. Para este problema, presentamos demostraciones que abarcan y extienden todos los resultados previos conocidos. Para finalizar, se prueba la existencia de un núcleo cuadrático para una generalización del problema de Vertex Cover parametrizado por el tamaño requerido del conjunto solución.
- Identificador 11489