Ingeniero Civil Matemático / La presente memoria tiene como objetivo un estudio general sobre componentes monocromáticas en multicoloreos de aristas de grafos completos, o dicho de otro modo, un coloreo de aristas de multigrafos completos. En particular, el tema de mayor importancia consiste en una generalización de una importante clase de problemas relacionados con la Conjetura de Ryser, la cual habla de una cota universal para el número de componentes conexas monocromáticas necesarias para cubrir todos los vértices de un grafo con sus aristas coloreadas, y donde tal cota solo depende del número de colores utilizados. Los resultados presentes en la memoria son fruto de distintas formas de abordar determinados problemas relacionados con la generalización mencionada y que, por fortuna, resultaron no solo ser útiles para los propósitos para los que fueron ideados, sino que algunos de ellos poseen interés por sí mismos. En primer lugar el motivo de estudio se centra en la cantidad de vértices que podemos asegurar para alguna de las componentes monocromáticas inducidas en un multicoloreo de aristas arbitrario en grafos bipartitos, para luego extender el resultado a grafos completos. Posteriormente se estudia una cota de vértices para multicoloreos de grafos tales que pueden ser cubiertos con tres componentes conexas monocromáticas y no pueden ser cubiertos con dos componentes conexas monocromáticas, pero si aislamos cualquiera de sus vértices entonces el resto de ellos pueden ser cubiertos por dos componentes monocromáticas. Este tipo de multicoloreos será llamado 3-crítico. Finalmente se introduce la generalización de un caso particular de la Conjetura de Ryser, que consiste en encontrar cotas, dependientes del número de colores utilizados, para multicoloreos de aristas de grafos completos. En particular, se restringe el estudio para multicoloreos de aristas uniformes, los cuales se definen como multicoloreos donde todas las aristas tienen el mismo número de colores. Primero se muestran cotas superiores generales, luego cotas inferiores, para finalmente estudiar determinados casos de manera particular y concluir cotas de manera estricta.

Ingeniero Civil Matemático / El objetivo principal de esta memoria es estudiar generalizaciones del problema de emparejamientos en línea. En un artículo seminal Karp, Vazirani y Vazirani estudiaron el siguiente problema de optimización: Dado un grafo bipartito G=(L,R,E) del que el lado L es conocido y el lado R llega en línea, se busca maximizar el tamaño de un emparejamiento, bajo la condición de que solo se puede emparejar un vértice en el momento en el que llega. Karp, Vazirani y Vazirani encuentran un algoritmo que es una (1-1/e)-aproximación para el problema. En esta memoria se generaliza el problema al caso en el que un lado no está fijo, o sea que vértices de ambos lados pueden llegar en línea. Se estudian tres modelos: el modelo adversarial, el modelo de orden aleatorio y el modelo fuera de línea. Para el modelo adversarial se definen algoritmos locales y se demuestra que ninguno de ellos puede ser mejor que una 1/2-aproximación. Para el modelo de orden aleatorio se encuentra un algoritmo cuya competividad está en el intervalo [0.696, 0.727]. Finalmente, para el modelo fuera de línea se encuentra un algoritmo óptimo cuya competividad es desconocida, pero se demuestra que está en el intervalo [0.526, 0.591].

Ingeniero Civil Industrial / Este trabajo de título tiene como objetivo fundamental analizar el aporte que se pueda generar a una metodología al introducir un análisis con medidas de centralidad de Teoría de Grafos, para la detección de Objetos Claves dentro de un sitio web. Para lograr esto existen una serie de objetivos específicos que permitirán concluir finalmente con respecto a la hipótesis de investigación planteada, destacando que se pretende incorporar herramientas que hasta ahora no se habían utilizado para este campo. Este trabajo es parte del procedimiento para optar al título de Ingeniero Civil Industrial, siendo parte de un proyecto FONDEF llamado Plataforma informática basada en web-intelligence y herramientas de análisis de exploración visual para la mejora de la estructura y contenido de sitios web (AKORI: Advanced Kernel for Ocular Research and Web Intelligence). AKORI es un proyecto co-creado entre el departamento de Ingeniería Industrial y la Facultad de Medicina de la Universidad de Chile. La justificación de este trabajo está relacionado con el crecimiento que ha sucedido en la web durante los últimos años. Este aumento exponencial de la cantidad de usuarios y páginas de Internet, ha llevado a que muchas empresas que basan su modelo de negocios en sus sitios web, tengan interés por destacar en la nube y tener los sitios optimizados para sus respectivos usuarios, produciendo una nueva rama de investigación sociológica, para ello se han desarrollado diversas metodologías que apuntan a mejorar el contenido y la estructura de los sitios web. Metodologías que tienen por lo general altos grados de subjetividad, siendo poco eficientes para definir exactamente las zonas u objetos que llaman más la atención para los distintos usuarios. La hipótesis de investigación propuesta plantea que es posible mejorar la metodología creada por Juan D. Velásquez al evaluar con medidas de centralidad de teoría de grafos, outputs obtenidos por experimentos ya realizados a 23 sujetos que navegaron libremente en la página web del MBA del departamento de Ingeniería Industrial, experimento que utilizó herramientas de eye-tracking, dilatación pupilar y EEG. Al mejorar la detección de Website Keyobjects aumentando la eficiencia de la metodología con el modelo propuesto, se estaría creando un pilar fundamental para el proyecto AKORI. Los WKO clasificados con esta metodología se compararon con otros trabajos previos y fueron evaluados finalmente por el webmaster determinando así la eficiencia de este nuevo trabajo y estableciendo las futuras líneas de acción a seguir. Si bien se demostró la hipótesis de investigación planteada, se cree que se podría desarrollar un mejor trabajo mejorando ciertas propuestas que se declaran en la parte final de este informe.

Ingeniero Civil Matemático / La computación distribuida, rama de las ciencias de la computación, se focaliza en estu- diar sistemas distribuidos, tales como internet, redes sociales o protocolos de mensajería. La información se encuentra distribuida entre las distintas entidades que conforman el sistema y el objetivo último es resolver algún problema global. Para ello las distintas entidades se comunican mediante los canales de la red hasta que encuentran la solución. Esta memoria comienza estudiando el problema de la degenerancia de un grafo en los modelos de computación distribuida UCAST y BCAST, donde la degenerancia de un grafo G se define como el máximo grado mínimo de un subgrafo F de G. Los modelos distribuidos UCAST y BCAST corresponden a redes completas de n individuos, los cuales se comunican de manera síncrona por los canales de la red en rondas. En el primer caso, cada individuo por ronda puede enviar diferentes mensajes por cada uno de sus canales. En el segundo caso, cada individuo por ronda envía a través de sus canales el mismo mensaje. En general, se suele decir que BCAST es una restricción de UCAST. Primero, se construye un protocolo aleatorio en el modelo UCAST que calcula una (1 + ε)- aproximación de la degenerancia en O(log n) rondas con mensajes de largo O(log n). En el modelo BCAST se demuestra que el problema de calcular la degenerancia es difícil en 1 ronda. Más específicamente, se demuestra que todo protocolo aleatorio de 1 ronda que calcule exactamente la degenerancia debe enviar un mensaje de largo Ω(n). En el mismo modelo, se construye un protocolo aleatorio de 2 rondas con mensajes de largo O(log 2 n) que calcula una (1 + ε)-aproximación de la degenerancia para grafos α-densos. Finalmente, se construye un protocolo determinista que calcula una (2 + ε)-aproximación de la degenerancia en O(log n) rondas con mensajes de largo O(log n). Como segunda parte de este trabajo, y motivado por el protocolo en BCAST que calcula una (2 + ε)-aproximación de la degenerancia, se estudia la siguiente dinámica sobre grafos: Durante cada iteración, eliminar todos los vértices que tengan grado a lo más el grado prome- dio del grafo +1. Se conjetura que para todo grafo G de n vértices la dinámica toma O(log n) iteraciones en vaciar el grafo. Se aborda el problema estudiando clases de grafos tales como: bosques, grafos planares, grafos con degenerancia acotada y grafos unión disjunta de cliques. Finalmente, se estudian diversos problemas en el modelo BCAST. Se comienza estudiando el problema de calcular el conjunto independiente maximal con un vértice fijo. Se prueba que el problema es difícil en 1 ronda y luego se contruye un protocolo que en O(log n) rondas, usando mensaje de largo O(log n), calcula el conjunto independiente. Se estudia también el problema de calcular el número cromático de un grafo. Se prueba que el problema resulta difícil en 1 ronda. Concluyendo el capítulo, se estudian los problemas de encontrar conjuntos dominantes de tamaño k y conjuntos -dominantes de tamaño k, en ambos casos se demuestra que los problemas son difíciles en 1 ronda. / Este trabajo ha sido parcialmente financiado por Proyecto Fondecyt 1130061

El problema de visualización de redes y/o grafos es un área muy estudiada en ciencias de la computación y también ha sido objeto de gran atención de investigadores en los últimos años. El presente trabajo está motivado a construir una aplicación que ayude en la visualización de grafos obtenidos de consultas al registro genealógico del Caballo Chileno. En la primera parte de este trabajo se realiza un estudio de algoritmos y técnicas para la visualización de grafos en dos dimensiones, revisando distintos autores y clasificación de éstos debido a su utilización en cierto tipo de grafo y también de restricciones introducidas a la visualización para considerarse válida y admisible. Luego se procede a plantear una solución a los requerimientos del problema: se decribe una arquitectura de la aplicación a construir, decisiones de diseño involucradas debido a restricciones del problema mismo y una descripción de la implementación. Más tarde se revisan los algoritmos construidos para generar consultas y recuperación de información y se detallan los algoritmos elegidos para la visualización de grafos generados de las consultas al registro genealógico equino. El resultado de utilizar las tecnologías propuestas hace que el requerimiento primario de la aplicación se cumpla. No obstante por el diseño de la misma, ésta puede extenderse para nuevas interfaces que se requieran. El desempeño de la aplicación se verificó utilizando pruebas sintéticas que fueron satisfactorias. Debido a la naturaleza de la información genealógica equina y a los tipos de consultas realizadas, éstas no estuvieron exentas del problema que representa la visualización de grandes grafos; problema observado y estudiado. Para lo último se plantearon aproximaciones que pudiesen a agregar valor a la aplicación diseñada para el usuario.

En el año 2004 el Consorcio de la World Wide Web (W3C) estandarizó un lenguaje de metadatos para la descripción de recursos en la Web denominado Resource Description Framework (RDF). La motivación fue el definir un lenguaje que sirva de base para el modelado extensible de dominios altamente interconectados y redes de información. La especificación de RDF puede ser vista, desde un punto de vista de base de datos, como un modelo de base de datos. En efecto, subyacente a RDF se encuentra un modelo el cual trae a la mente la noción de datos con estructura de grafo. Por otra parte, la cifra creciente de información representada en el lenguaje RDF ha sido acompañada de varias propuestas sobre como almacenar y consultar datos RDF. En consecuencia, resulta natural el estudio de RDF desde un punto de vista de base de datos. El objetivo principal de esta tesis es el estudio de RDF desde una perspectiva de base de datos. Nuestro estudio se concentra en el modelado de base de datos, enfocándonos en modelos particulares llamados modelos de base de datos de grafo, los cuales parecen estar más relacionados a RDF desde un punto de vista teórico. Asimismo, esta tesis sigue de cerca los desarrollos del W3C en el sentido de entregar a RDF el soporte de un modelo de base de datos, en particular desarrollar los aspectos de consulta de datos. La principal contribución de la tesis es haber clarificado y desarrollado la relación entre RDF y los modelos de base de datos de grafo. Para esto, primero se estudió RDF como un modelo de base de datos. Segundo, se realizó una conceptualización del área de modelos de base de datos de grafo. Tercero, se propuso un conjunto deseable de propiedades de grafo las cuales deberían ser soportadas por un lenguaje de consulta ideal para RDF. Cuarto, se demostró que el lenguaje de consulta estándar definido por el W3C, denominado SPARQL, no soporta las consultas de grafo esenciales que se esperaría encontrar en un lenguaje de consulta para bases de datos de grafo. Esto fue conseguido al estudiar y determinar el poder expresivo de SPARQL. Finalmente, y debido a los resultados anteriores, nos concentramos en la aplicación de los modelos de bases de datos de grafo a la visualización de datos, esto al definir formalmente y caracterizar un modelo de visualización de grafo para RDF.

Ingeniero Civil Matemático / Un coloreo de aristas de un grafo se llama γ-promedio si es que el número promedio de colores incidentes a cada vértice es a lo más γ. Dados n, m enteros positivos y γ un real positivo, el número de Turán promedio coloreado T(n, K_m, γ-promedio) corresponde a la máxima cantidad de aristas que puede tener un grafo de n vértices de manera que exista un coloreo γ-promedio que no contenga ninguna copia monocromática de K_m. Esta noción fue introducida por Caro, quien observa que la expansión (blow-up) de un grafo completo γ-promedio coloreado sin copias monocromáticas de K_m también es γ-promedio coloreado y tampoco posee copias monocromáticas de K_m. Con ello, Caro se pregunta de si el máximo de aristas buscado se alcanza en la expansión de un grafo completo γ-promedio coloreado que maximice el número de vértices bajo la condición de no contener una copia monocromática de K_m (un coloreo extremal para el número de Ramsey γ-promedio). Yuster probó que la respuesta es afirmativa para el caso m=3 y γ=2, y además conjeturó que la respuesta es siempre afirmativa para todos los γ = ℓ ∈ N. En la presente memoria se demuestra esta conjetura de Yuster cuando m >= ℓ(ℓ+1)+1. Por otro lado, se demuestra también que la respuesta a la pregunta de Caro es negativa para un conjunto no numerable de valores de γ ∉ N.

Magíster en Ciencias, Mención Computación / La estructura de la Web se puede modelar como un grafo, donde las páginas son los nodos y los hipervínculos las aristas. Estos grafos Web son ampliamente utilizados para diversas tareas de análisis de la Web, tales como el cálculo de Page-Rank o la detección de spam en la Web, entre otras. Una de las limitantes que se presentan al trabajar con estos grafos es su tamaño, por ejemplo, el 2005 se calculó que la Web pública y estática tenía 11.5 mil millones de nodos, y unas 15 aristas por nodo, lo que requiere más de 600 GB para su representación plana. De aquí surge la motivación de este trabajo, que consiste en la creación de estructuras de datos comprimidas para representar grafos de la Web. Una estructura comprimida busca almacenar la mayor cantidad de datos en el menor espacio posible, ya sea en memoria principal o en disco, soportando las consultas de interés sin la necesidad de descomprimir la estructura en su totalidad. La principal ventaja de estas estructuras es que se puede evitar mantener la información en disco o se disminuye la cantidad de transferencias necesarias. Esto es de vital importancia dado que el disco puede llegar a ser un millón de veces más lento que la memoria principal. Entre los resultados más importantes de este trabajo se presenta una estructura comprimida para grafos de la Web que mejora el estado del arte, ofreciendo el mejor compromiso espacio-tiempo conocido para recuperar listas de adyacencia. Además se muestra cómo extender esta estructura para soportar consultas más complejas, como vecinos reversos, manteniendo los requerimientos de espacio. Como productos agregados se incluyen resultados experimentales y propuestas para el problema de Rank y Select sobre secuencias generales, incluyendo estructuras no implementadas antes. Los resultados derivan en mejoras inmediatas para índices comprimidos para texto, en los cuales se reduce el espacio utilizado por los mejores índices existentes, a veces incluso sin penalización en el tiempo de búsqueda. Además se presenta un algoritmo aproximado para comprimir utilizando el método Re-Pair cuando la memoria principal es limitada. También se obtienen resultados en estructuras comprimidas para relaciones binarias, presentándose una nueva propuesta que, además de utilizar espacio proporcional a la entropía de la relación binaria, permite dinamizar la estructura, vale decir, aceptar inserciones y borrados de pares en la relación.

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.

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