Una gráfi ca es un conjunto de objetos llamados vértices, junto con un conjunto de objetos llamados aristas que unen a los vértices. Una gráfi ca geométrica es una representación en el plano de una gráfi ca. Una H-crossing family es un conjunto de gráfi cas geométricas que cumple dos propiedades: 1) cada elemento del conjunto es una representación de una gráfi ca H, 2) siempre que tomemos dos elementos del conjunto estos se cruzan. Un thrackle es un conjunto de segmentos que se intersectan dos a dos, es decir, siempre que elegimos dos segmentos estos se cruzan o comparten un punto. El tamaño de una H-crossing family es el número de elementos en el conjunto. Decimos que un thrackle es máximo si su número de segmentos es igual a su número de puntos. Denotamos como 2K2 la gráfi ca que tiene dos aristas disjuntas en vértices. Denotamos como K1;3 a la gráfica bipartita completa con 1 y 3 vértices.
En esta tesis realizamos búsquedas computacionales para encontrar la 2K2-crossing family y la K1;3-crossing family más grande de tal forma que exista al menos una 2K2-crossing family y una K1;3-crossing familiy para cada conjunto con 8, 9 y 10 puntos. Tambien realizamos búsquedas para encontrar thrackles máximos sobre todos los conjuntos de 8, 9 y 10 puntos. Encontramos que existe al menos una 2K2-crossing families y K1;3-crossing families de tamaño bn 4 c para cada conjunto de 8, 9 y 10 puntos. Encontramos también que no todos los conjuntos de 8, 9 y 10 puntos tienen un thrackle máximo y encontramos el número de conjuntos que s lo tienen. Damos algunas características que cumplen los conjuntos que sí tienen thrackle máximo.
Abstract
A graph is de ned by a set V of vertices and a set E of edges de ned over V . A geometric graph is a drawing of a graph in the plane such that each vertex is represented by a point, and each edge is represented by a segment between the corresponding two points. A H-crossing family is a set of geometric graphs where, each element is a drawing of a graph H in the plane and every two elements cross. A thrackle is a set of edges where every two edges intersect. The size of an H-crossing family is the number of elements in the set. A thrackle is maximum if it has as many edges as vertices.
In this thesis we present some computational searches to nd the maximum size of a 2K2-crossing family, and a K1;3-crossing family, in point sets with 8, 9 and 10 points. Every set of 8, 9 and 10 points must have a least one 2K2-crossing family or a K1;3-crossing family of such a maximum size. We also present computational searches to nd maximum thrackles in point sets of 8, 9 and 10 points. We nd that there is a least one 2K2-crossing family and a K1;3-crossing family of size bn 4 c on every set with 8, 9 and 10 points. We also nd that not every set with 8, 9 and 10 points have a maximum thrackle. We show which are the point sets of size 8, 9 and 10 that have a maximum thrackle and we characterized such sets.
