• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 1
  • Tagged with
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
1

Gemelos de árboles con una cantidad contable de ends

Araneda Galarce, Sergio Andrés January 2013 (has links)
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.

Page generated in 0.0662 seconds