El presente trabajo presenta una aplicación de la teoría de grafos en la optimización del sistema de transporte y la reducción de costos en la operación logística de acopio de jalapeños en una empresa agroindustrial. AIMSA opera en la sierra y selva central del Perú, en el 2013 y 2014 ha logrado un crecimiento de 20% de crecimiento en ventas de los cuales el jalapeño representa el 50%. Uno de los problemas que se ha identificado es que el acopio de los jalapeños para trasladarse hasta la planta de procesamiento afronta tres problemas principales: el primero que las llegadas no son en horarios regulares, existiendo retrasos de hasta dos días en el cumplimiento del programa semanal, el segundo es que se usaba unidades de transporte sin medir la capacidad contrastado con la cantidad de jalapeño cosechado por el operador productivo (agricultor) y tercero que el recorrido por cada operador productivo no estaba establecido. Partiendo del programa semanal de cosecha se ha agrupado en “clusters” esto nos ha permitido asignar la unidad de transporte con capacidades de acuerdo a los Kg, de cosechas, el procedimiento se ajusta “agrupar primero y rutear después”, luego hicimos el ruteo con la ayuda de Grafos v 1.2.3 teniendo como restricciones la capacidad del vehículo y la oferta de materia prima de cada operador productivo, cabe resaltar que esto cambia de semana en semana de acuerdo a los “clusters” formados, finalmente se realizó el programa de la flota de vehículos. Los resultados obtenidos fueron: 144 rutas con un recorrido total de 5,838 Km. se han acopiado 1,365,379 Kg de Jalapeño utilizando una capacidad de flota de 1,480,595 Kg, con un costo unitario de transporte de S/. 0.159 cada Kg. Finalmente, para validar el método de dos fases realizamos la programación lineal entera y lo corrimos en AMPL encontrando oportunidades aun por mejorar tanto en recorrido y en costos. / Tesis

Definición de un grafo. Implementación de un grafo. Problemas resueltos con grafos. Algoritmos de la ruta más corta. Algoritmo de Dijkstra.

Algoritmo Ford Fulkerson para Flujo Máximo en un grafo.

El objetivo de esta tesis ha sido diseñar nuevos algoritmos en el campo del análisis de observabilidad de procesos industria-les empleando teoría de grafos y conceptos avanzados de ciencias de la computación. Como resultado de estas inves-tigaciones se ha logrado el desarrollo de técnicas robustas y eficientes especialmente diseñadas para la clasificación de variables no medidas en procesos industriales con modelos matemáticos fuertemente no lineales. Mediante el empleo de los nuevos algoritmos propuestos en esta tesis ahora es posible el tratamiento en forma precisa y eficiente de proble-mas que no podían ser resueltos por los métodos de observabi-lidad clásicos, o que requerían una estricta simplificación de su modelo matemático para que estas técnicas pudieran ser aplicadas. Los métodos desarrollados se basan fundamental-mente en la permutación de la matriz de ocurrencia correspon-diente al sistema de ecuaciones que modela la planta. Estos reordenamientos estructurales emplean técnicas de descompo-sición de grafos, digrafos, bigrafos e hipergrafos. Todas las técnicas desarrolladas lograron un muy buen desempeño, res-pecto de las metodologías existentes, al ser empleadas en la clasificación de variables no medidas de modelos matemáticos complejos correspondientes a problemas industriales reales. Finalmente, se diseñó e implementó un sistema de soporte de decisión que engloba toda la experiencia adquirida en clasifi-cación de variables a lo largo de este trabajo de tesis. El software desarrollado resulta eficiente, robusto y amigable, asistiendo al usuario en forma versátil y confiable en la com-pleja tarea de establecer la ubicación más apropiada para los sensores que controlan el correcto funcionamiento de una planta real. El paquete posibilita analizar en forma rigurosa plantas de cualquier dimensión, incluso las de gran enver-gadura.

Magíster en Ciencias de la Ingeniería, Mención Matemáticas Aplicadas. Ingeniero Civil Matemático / Un conjunto de vértices de un grafo se dice convexo si contiene a los vértices de todos los caminos mínimos entre sus vértices. El problema de determinar si un grafo tiene una partición en p conjuntos convexos es NP-completo, pero hay diversas familias de grafos en las que se puede resolver en tiempo polinomial. El foco principal de este trabajo es estudiar el problema de la p-partición convexa en una familia de grafos definida recursivamente al reemplazar los vértices de un bosque por grafos de ésta. Esta familia resulta ser cerrada para subgrafos inducidos. Sin embargo, no queda totalmente determinada la familia de subgrafos prohibidos que determina a esta familia. Además, estos grafos resultan ser perfectos, por lo que varios problemas combinatoriales resultan tener soluciones polinomiales en esta familia. Además, se entrega un algoritmo polinomial para reconocer si un grafo pertenece a esta familia. Para atacar el problema de las particiones convexas en este contexto, combinaremos, mediante programación dinámica, particiones en subgrafos tales que sus particiones convexas son de tres tipos: todos los vértices, particiones en cliques y particiones en cliques más un conjunto localmente convexo. En el caso de las particiones en cliques, se entrega un algoritmo polinomial que lo resuelve. / Este trabajo ha sido parcialmente financiado por CONICYT mediante Proyecto Basal PFB 03

Ingeniero Civil Matemático / Se estudia la estructura de grafos completos de tamaño apropiado, con una coloreación de sus aristas en dos colores, de manera tal que no presentan como subgrafos monocromáticos a ciertos tipos de grafos específicos. En este caso se considera el caso de un ciclo impar C_n con n vértices y una rueda W_n := K_1 + C_n con n+1 vértices; en el caso en que n es impar. Se muestra que para n impar y todo grafo completo de tamaño apropiado, con una coloreación de sus aristas en azul y rojo que no contenga como subgrafo monocromático rojo a C_n ni como subgrafo monocromático azul a W_n; eliminando a lo más dos vértices se obtiene una partición de sus vértices en tres conjuntos que inducen grafos completos de color rojo, y aristas formando un grafo tripartito completo. Dicho resultado se puede ver como una generalización de resultados presentados por Nikiforov y Schelp; y como una suerte de recíproca a cotas conocidas para números de Ramsey asimétricos. Como resultado secundario de la demostración se obtienen dos cotas para el número de Ramsey de r(C_{2k+1}, W_{2k+2}): una es más fina para valores pequeños de k y la otra es mejor en el caso asintótico. Los valores exactos de dichos números de Ramsey son, en este instante, un problema abierto. Las cotas expresadas son una aproximación a los valores que han sido conjeturados y permiten ver que, al menos a un nivel asintótico, dichos resultados son ciertos.

Ingeniera Civil Matemática / En la presente memoria se considera la relación entre coloreamiento de vértices y la noción de inmersión. Específicamente, se estudia una conjetura propuesta por Abu-Khzam y Langston, la cual dice que el grafo completo de tamaño t está inmerso en todo grafo t-cromático. En primer lugar, se ven algunos resultados generales de inmersiones y se prueba que la conjetura se cumple para los grafos cuyo complemento no contiene ciclos inducidos de largo cuatro y también para los grafos tales que todo conjunto de cinco vértices induce un subgrafo con al menos seis aristas. Luego, se da una breve mirada a una nueva relación definida, en un intento de generalizar la relación de inmersión. Finalmente, se estudia en detalle una clase especial de grafos, aquella de los grafos sin conjunto independiente de tamaño tres. Se presentan condiciones suficientes para que se cumpla la conjetura de Abu-Khzam y Langston. Luego, se introduce una nueva conjetura, implicada por la conjetura de Abu-Khzam y Langston y se demuestra una versión un tanto más débil que ésta. Se prueba además, que ambas conjeturas son equivalentes. Por último, se exhiben una serie de propiedades que debería cumplir un contraejemplo mínimo, en caso de existir alguno.

Doctora en Ciencias, Mención Computación / Con la popularidad de la Web y, mas recientemente, el amplio uso de las redes sociales, la necesidad de procesar y encontrar información en grafos muy grandes impone varios desafíos: Cómo procesar grafos muy grandes e cientemente, dado que probablemente son muy grandes para la memoria disponible, o incluso si la memoria es su ciente, realizar un paso sobre el grafo es todavía caro computacionalmente? Cómo almacenar esos grafos e cientemente, para ser archivados, o para ejecutar algoritmos de grafos? Cómo descubrir información relevante tal como componentes densos, comunidades, u otras estructuras? Se han propuesto tres enfoques para manejar grafos grandes. El primero es usar formatos de grafos comprimidos que permiten consultas de navegación básicas directamentee sobre la estructura comprimida, sin la necesidad de descompresión. Esto permite simular cualquier algoritmo de grafo en memoria principal usando mucho menos espacio que la representación plana. Una segunda línea de investigación se focaliza en usar modelos de stream o semi- stream de datos de manera de procesar secuencialmente, idealmente en un paso sobre el disco, usando una cantidad limitada de memoria principal. La tercera línea es el uso de sistemas distribuidos y paralelos donde la memoria es agregada sobre múltiples unidades de procesamiento para procesar el grafo en paralelo. En esta tesis presentamos varios enfoques para manejar grafos grandes (con arcos sin etiquetas) considerando los tres enfoques. Primero, buscamos por patrones que aparecen en grafos de la Web y redes sociales los que podemos representar en forma compacta, en particular mostramos como generalizar algoritmos para encontrar cliques o bicliques para encontrar sub-estructuras densas que comprimen ambas. Segundo, basado en estos subgrafos densos, proponemos esquemas comprimidos que soportan consultas de vecinos directos y reversos, así como otras consultas mas complejas sobre subgrafos densos. Algunas de las contribuciones combinan técnicas del estado del arte mientras otras incluyen representaciones comprimidas novedosas basadas en estructuras de datos compactas. Encontrar subgrafos densos es una tarea que consume tiempo y espacio, así que proporcionamos algoritmos de streaming and algoritmos de memoria externa para descubrir subgrafos densos, asi como también algoritmos distribuidos para construir las estructuras básicas que usamos para las representaciones comprimidas.

Los procesos de percolación son modelos que sirven para describir el flujo de líquidos en medios porosos desordenados. Este trabajo es una introducción a los procesos de percolación independiente sobre grafos planos. Primero desarrollamos la teoría de grafos y de probabilidad involucrada para luego definir los modelos de percolación de enlaces y de sitios (bond y site, respectivamente, por sus nombres en inglés), en los cuales los objetos de interés son las aristas y los vértices del grafo, respectivamente. Después exhibimos las cualidades más básicas de estos modelos y las características cuantitativas usadas en su estudio haciendo hincapié en su comportamiento de "transición de fase": un pequeño cambio de los parámetros del modelo resulta en un cambio abrupto de su comportamiento global. En este caso, esta transición de fase ocurre en una probabilidad crítica que, en general, es dificil de hallar exactamente. La excepción son algunos grafos "simétricos", para los que se cumple una interesante relación entre sus probabilidades críticas y que explicaremos en este trabajo. Finalmente, presentamos algoritmos computacionales para simular los modelos de percolación de enlaces y de sitios. Además, utilizamos estos algoritmos para observar gráficamente el comportamiento de transición de fase y los adaptamos para estimar probabilidades críticas que no han podido hallarse analíticamente. / Tesis

Ingeniero Civil Matemático / Dos grafos son gemelos si son mutuamente subgrafos entre sí. En grafos finitos la única forma de que dos grafos sean mutuamente subgrafos entre sí es que sean isomorfos. Sin embargo, en grafos infinitos existen grafos que se incluyen mutuamente y no isomorfos entre sí. Bonato y Tardif [3] se preguntaron por la cantidad de gemelos que puede tener un grafo. La conjetura de alternativa en árboles plantea que si un árbol tiene gemelos no isomorfos a él, entonces tiene infinitos gemelos. En el presente trabajo se presenta una demostración de la conjetura para árboles localmente finitos con una cantidad contable de ends. Se comienza realizando una revisión general de los conceptos y teoremas de grafos infinitos. Se introducen los conceptos básicos de grafos infinitos (rayo, doble rayo, end etc). Luego se estudia también una topología definible para un grafo infinito, que describe de mejor manera el grafo y sus ends que es de relevancia en la demostración dada posteriormente. Posteriormente se estudian los conceptos, definiciones y teoremas propios de la conjetura. Se revisarán los trabajos hechos hasta ahora, las ideas que han surgido a partir de intentos para demostrar la conjetura y la descripción de un grafo con propiedades interesantes. A continuación se estudia en detalle la relación subgrafo en grafos infinitos. Se introduce el concepto de morfismo y se muestra su relación con los conceptos de subgrafo e isomorfismo. También se estudia el grupo de automorfismos del doble rayo y de árboles finitos. Se mostrará además una forma de definir isomorfismos entre árboles infinitos localmente finitos a partir de isomorfismos locales. También se estudiará la construcción de isomorfismos definidos por componentes. Luego, se demuestra la conjetura para árboles con una cantidad finita de ends. Primero se demuestra la conjetura para árboles con exactamente un end, luego con exactamente dos ends y finalmente para árboles con más de 2 ends. Finalmente, se demuestra la conjetura para árboles con una cantidad infinita contable de ends. Se introduce el concepto de centro-end y a partir de éste se demostrará una extensión de un teorema dado por Halin [7] para árboles con una cantidad contable de ends. Este resultado fue dado por Polat y Sabidussi [9] para automorfismos, se presenta una demostración alternativa que también abarca endomorfismos. Usando esta extensión se demuestra la conjetura. Se define el concepto de ecuación gráfica, que junto con el teorema extendido de Halin permiten demostrar la conjetura en el caso más difícil.