En la presente tesis se analiza el problema del coloreado de grafos tanto desde el punto de vista teórico como en relación a la resolución del problema mediante técnicas algorítmicas, algunas de las cuales se describen por vez primera. Se estudian asimismo distintas variaciones del problema simple del coloreado incluyendo el coloreado de vértices etiquetados, en que se asigna un número variable de colores a cada vértice, y el coloreado con aristas etiquetadas, en el que los colores asignados a vértices adyacentes deben guardar una distancia mayor o igual a la etiqueta de la arista que los une, así como combinaciones de ambos.Las técnicas descritas para el coloreado de grafos han sido posteriormente adaptadas a un problema de asignación de frecuencias en telefonía móvil habiéndose aplicado los algoritmos sobre distintos tipos de redes celulares. Las distintas redes analizadas pueden incorporar o no conmutación en frecuencia, variando la naturaleza del problema en cada caso. Para el caso de coloreado múltiple asociado al problema de asignación de frecuencias se ha descrito un conjunto de matrices asociadas a un grafo G(V,E) y un coloreado simple C que permiten reasignar colores a distintos vértices de G(V,E) aprovechando colores de C. Este reciclaje, en combinación con las métodos algorítmicos aplicados en coloreados simples, ha permitido resolver con eficiencia el problema del multicoloreado de grafos y en consecuencia el problema de asignación de frecuencias en redes celulares.En la segunda parte de la tesis se estudian las redes pequeño-mundo y se describen pautas deterministas para su obtención. De este modo se describe en primer lugar el modelo probabilista definido por Watts y Strogatz y se analiza la aparición de autoorganización crítica en las redes pequeño-mundo (caracterizadas por un apiñamiento elevado y un diámetro o distancia máxima entre vértices reducido) para a continuación ampliar el concepto sobre modelos deterministas. Se ha demostrado de este modo la posibilidad de obtener redes pequeño-mundo sobre grafos circulantes, mallas toroidales e hipercubos.Finalmente se ha probado la universalidad del efecto pequeño-mundo, es decir, la posibilidad de recortar arbitrariamente el diámetro de un grafo genérico G(V,E) sin que se produzcan variaciones significativas en su topología local (medida a partir del factor de clustering o apiñamiento del grafo), explicando así la ubicuidad de las redes pequeño-mundo y su descripción en entornos de todo tipo: social, biológico, industrial, matemático, etcétera.
| Identifer | oai:union.ndltd.org:TDX_UPC/oai:www.tdx.cat:10803/5844 |
| Date | 23 July 2001 |
| Creators | Ozón Górriz, Javier |
| Contributors | Comellas Padró, Francesc De Paula, Universitat Politècnica de Catalunya. Facultat de Matemàtiques i Estadística |
| Publisher | Universitat Politècnica de Catalunya |
| Source Sets | Universitat Politècnica de Catalunya |
| Language | English |
| Detected Language | Spanish |
| Type | info:eu-repo/semantics/doctoralThesis, info:eu-repo/semantics/publishedVersion |
| Format | application/pdf |
| Source | TDX (Tesis Doctorals en Xarxa) |
| Rights | ADVERTIMENT. L'accés als continguts d'aquesta tesi doctoral i la seva utilització ha de respectar els drets de la persona autora. Pot ser utilitzada per a consulta o estudi personal, així com en activitats o materials d'investigació i docència en els termes establerts a l'art. 32 del Text Refós de la Llei de Propietat Intel·lectual (RDL 1/1996). Per altres utilitzacions es requereix l'autorització prèvia i expressa de la persona autora. En qualsevol cas, en la utilització dels seus continguts caldrà indicar de forma clara el nom i cognoms de la persona autora i el títol de la tesi doctoral. No s'autoritza la seva reproducció o altres formes d'explotació efectuades amb finalitats de lucre ni la seva comunicació pública des d'un lloc aliè al servei TDX. Tampoc s'autoritza la presentació del seu contingut en una finestra o marc aliè a TDX (framing). Aquesta reserva de drets afecta tant als continguts de la tesi com als seus resums i índexs., info:eu-repo/semantics/openAccess |
Page generated in 0.003 seconds