Registro:
| Documento: | Tesis de Grado |
| Título: | Sobre la aplicación iterada del operador clique en grafos y su convergencia lineal |
| Autor: | Taravilse, Leopoldo |
| Editor: | Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales |
| Publicación en la web: | 2025-06-12 |
| Fecha de defensa: | 2016 |
| Fecha en portada: | 2016 |
| Grado Obtenido: | Grado |
| Título Obtenido: | Licenciado en Ciencias de la Computación |
| Departamento Docente: | Departamento de Computación |
| Director: | Bonomo, Flavia |
| Director Asistente: | Frías Armenta, Martín Eduardo |
| Jurado: | Durán, Guillermo Alfredo |
| Idioma: | Español |
| Formato: | PDF |
| Handle: |
http://hdl.handle.net/20.500.12110/seminario_nCOM000656_Taravilse |
| PDF: | https://bibliotecadigital.exactas.uba.ar/download/seminario/seminario_nCOM000656_Taravilse.pdf |
| Registro: | https://bibliotecadigital.exactas.uba.ar/collection/seminario/document/seminario_nCOM000656_Taravilse |
| Ubicación: | Dep.COM 000656 |
| Derechos de Acceso: | Esta obra puede ser leída, grabada y utilizada con fines de estudio, investigación y docencia. Es necesario el reconocimiento de autoría mediante la cita correspondiente. Taravilse, Leopoldo. (2016). Sobre la aplicación iterada del operador clique en grafos y su convergencia lineal. (Tesis de Grado. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de http://hdl.handle.net/20.500.12110/seminario_nCOM000656_Taravilse |
Resumen:
Uno de los primeros conceptos que se introdujo con la teoría de grafos fue el de clique. Una clique es un subgrafo maximal completo, es decir, un subgrafo donde todos los pares de vértices están conectados entre sí, y que además es maximal respecto de esa propiedad. En 1972, luego de que Cook [8] introdujera el concepto de problema NP-completo, Karp [21] demostró que el problema de hallar una clique máxima en un grafo general es NP-hard, y el de determinar si una clique es m´axima es NP-completo. Esto hizo que muchos especialistas de la teoría de grafos estudiarán el comportamiento de las cliques en grafos generales y en familias particulares de grafos. También en 1971, Roberts y Spencer [28] caracterizaron los grafos clique (aquellos grafos donde los v´ertices son las cliques maximales de un grafo y las aristas ocurren entre cliques con intersección no vacía), y en 1972, Hedetniemi y Slater [19] introdujeron el concepto de grafos iterados de cliques, que consiste en partir en un primer paso de un grafo G, y en cada paso calcular el grafo clique del grafo del paso anterior. Los mismos Hedetniemi y Slater demostraron en [19] que existen grafos tales que al aplicarles el operador clique reiteradas veces convergen al grafo trivial, así como también grafos que convergen a un ciclo de grafos no triviales. Los primeros se llaman grafos k-nulos y los segundos k-periódicos. Los grafos k-nulos y los k-periódicos se llaman también grafos k-convergentes. En dicho trabajo los autores presentan ejemplos de grafos k-nulos y de grafos k-convergentes de periodos 1 y 2. Un año después, Victor Neumann-Lara descubre que existen familias de grafos k-divergentes dando como ejemplo a los octaedros, y Escalante reporta en 1973 [12] este descubrimiento de Neumann-Lara mostrando que además existen grafos k-periódicos de período p para todo p ≥ 1. A lo largo de los a˜nos se ha ido estudiando el comportamiento de los grafos iterados de cliques, como por ejemplo cuando Larrión y Neumann-Lara [22] demostraron que existen familias infinitas de grafos que divergen polinomialmente para cualquier grado (es decir, existen familias que divergen linealmente, cuadráticamente, etc). En esta tesis presentaremos dos familias de grafos que convergen linealmente, una pregunta abierta hasta el momento. La primera de ellas decrece su número de v´ertices de a 4 o más, mientras que la segunda decrece su número de vértices de a 3 o más, quedando abierta la pregunta de si existen familias de grafos que convergen linealmente de a 1 o 2 vértices. Para estas familias de grafos, daremos algoritmos polinomiales de reconocimiento, es decir, que en tiempo polinomial podremos saber si un grafo pertenece o no a esta familia. iv v A su vez, presentaremos familias de grafos que son auto-cliques y que son homeomorfas a distintos espacios topológicos. Los primeros grafos que mostraremos son homeomorfos a bandas de Moebious, a botellas de Klein y a planos proyectivos, y a su vez mostraremos una forma de combinar estos grafos para generar grafos homeomorfos a otros espacios topológicos.
Citación:
---------- APA ----------
Taravilse, Leopoldo. (2016). Sobre la aplicación iterada del operador clique en grafos y su convergencia lineal. (Tesis de Grado. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de https://hdl.handle.net/20.500.12110/seminario_nCOM000656_Taravilse
---------- CHICAGO ----------
Taravilse, Leopoldo. "Sobre la aplicación iterada del operador clique en grafos y su convergencia lineal". Tesis de Grado, Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales, 2016.https://hdl.handle.net/20.500.12110/seminario_nCOM000656_Taravilse
Estadísticas:
Descargas mensuales
Total de descargas desde :
https://bibliotecadigital.exactas.uba.ar/download/seminario/seminario_nCOM000656_Taravilse.pdf
Distrubución geográfica
