¿Los gráficos están determinados únicamente por sus subgrafos?
De manera informal, la conjetura de reconstrucción en la teoría de grafos dice que los gráficos están determinados únicamente por sus subgrafos. Se debe a Kelly [1] y Ulam . [2] [3]
Declaraciones formales
Dado un gráfico , un subgrafo eliminado de vértice dees un subgrafo formado eliminando exactamente un vértice de. Por definición, es un subgrafo inducido de.
Para un gráfico , la baraja de G , denotada, es el conjunto múltiple de clases de isomorfismo de todos los subgrafos de vértice suprimido de. Cada gráfico ense llama tarjeta . Se dice que dos gráficos que tienen el mismo mazo son hipomórficos .
Con estas definiciones, la conjetura se puede enunciar como:
- Conjetura de reconstrucción: dos gráficos hipomórficos cualesquiera en al menos tres vértices son isomorfos.
- (El requisito de que las gráficas tengan al menos tres vértices es necesario porque ambas gráficas en dos vértices tienen los mismos mazos).
Harary [4] sugirió una versión más fuerte de la conjetura:
- Conjetura de reconstrucción de conjuntos: dos gráficos cualesquiera en al menos cuatro vértices con los mismos conjuntos de subgráficos suprimidos por vértices son isomorfos.
Dado un gráfico , un subgrafo con borde eliminado dees un subgrafo formado eliminando exactamente un borde de.
Para un gráfico , el tablero de borde de G , denotado, es el conjunto múltiple de todas las clases de isomorfismos de subgrafos con borde eliminado de. Cada gráfico ense llama una tarjeta de borde .
- Conjetura de reconstrucción de bordes: (Harary, 1964) [4] Dos gráficos cualesquiera con al menos cuatro bordes y que tengan las mismas cubiertas de borde son isomorfos.
Propiedades reconocibles
En el contexto de la conjetura de la reconstrucción, una propiedad de un gráfico se llama reconocible si se puede determinar la propiedad a partir del tablero de un gráfico. Las siguientes propiedades de los gráficos son reconocibles:
- Orden del gráfico : el orden de un gráfico, es reconocible por como el multiset contiene cada subgrafo de creado eliminando un vértice de . Por eso [5]
- Número de aristas del gráfico : el número de aristas en un gráfico. con vértices es reconocible. Primero tenga en cuenta que cada borde de ocurre en miembros de . Esto es cierto por la definición de lo que asegura que cada borde se incluye cada vez que cada uno de los vértices con los que incide se incluye en un miembro de , por lo que se producirá una ventaja en cada miembro de excepto en los dos en los que se eliminan sus puntos finales. Por eso, dónde es el número de aristas en el i- ésimo miembro de. [5]
- Secuencia de grados: la secuencia de grados de un gráfico.es reconocible porque el grado de cada vértice es reconocible. Para encontrar el grado de un vértice—El vértice ausente del i- ésimo miembro de-, examinaremos el gráfico creado eliminándolo, . Este gráfico contiene todos los bordes que no inciden con, Así que si es el número de aristas en , luego . Si podemos decir el grado de cada vértice en la gráfica, podemos decir la secuencia de grados de la gráfica. [5]
- (Vértice-) Conectividad : por definición, un gráfico es-vertex-connected al eliminar cualquier vértice crea un -Gráfico conectado al vértice; por tanto, si cada carta es una-Gráfico conectado al vértice, sabemos que el gráfico original fue -conectado al vértice. También podemos determinar si la gráfica original estaba conectada, ya que esto equivale a tener dos de losestar conectado. [5]
- Polinomio de Tutte
- Polinomio característico
- Planaridad
- Los tipos de árboles de expansión en un gráfico
- Polinomio cromático
- Ser un gráfico perfecto o un gráfico de intervalo , o algunas otras subclases de gráficos perfectos [6]
Verificación
Brendan McKay verificó tanto las conjeturas de reconstrucción como de reconstrucción de conjuntos para todos los gráficos con un máximo de 11 vértices . [7]
En sentido probabilístico, Béla Bollobás ha demostrado que casi todos los gráficos son reconstruibles. [8] Esto significa que la probabilidad de que un gráfico elegido al azar en vértices no es reconstruible pasa a 0 como va al infinito. De hecho, se demostró que no solo casi todas las gráficas son reconstruibles, sino que en realidad no es necesario todo el mazo para reconstruirlas; casi todas las gráficas tienen la propiedad de que existen tres cartas en su mazo que determinan de manera única el gráfico.
Familias de gráficos reconstruibles
La conjetura se ha verificado para una serie de infinitas clases de gráficos (y, trivialmente, sus complementos).
- Gráficos regulares [9] : los gráficos regulares se pueden reconstruir mediante la aplicación directa de algunos de los hechos que se pueden reconocer a partir de un gráfico. Dado un-Gráfico regular y su cubierta , podemos reconocer que el mazo es de un gráfico regular reconociendo su secuencia de grados. Examinemos ahora un miembro de la baraja, . Este gráfico contiene cierto número de vértices con un grado de y vértices con un grado de . Podemos agregar un vértice a este gráfico y luego conectarlo al vértices de grado para crear un -Gráfico regular que es isomorfo al gráfico con el que comenzamos. Por lo tanto, todos los gráficos regulares son reconstruibles a partir de sus cubiertas. Un tipo particular de gráfico regular que es interesante es el gráfico completo. [5]
- Árboles [9]
- Gráficos desconectados [9]
- Gráficos de intervalo unitario [6]
- Gráficos separables sin vértices finales [10]
- Gráficos planos máximos
- Gráficos planos exteriores máximos
- Gráficos planos exteriores
- Bloques críticos
Reducción
La conjetura de la reconstrucción es cierta si todas las gráficas conectadas a 2 son reconstruibles. [11]
Dualidad
La conjetura de reconstrucción de vértices obedece a la dualidad de que si se puede reconstruir a partir de su mazo de vértices , luego su complemento se puede reconstruir a partir de de la siguiente manera: Empiece con , tome el complemento de cada tarjeta para obtener , usa esto para reconstruir , luego vuelva a tomar el complemento para obtener .
La reconstrucción de bordes no obedece a tal dualidad: de hecho, para algunas clases de grafos reconstruibles de bordes no se sabe si sus complementos son reconstruibles de bordes.
Otras estructuras
Se ha demostrado que, en general, lo siguiente no es reconstruible:
- Dígrafos : Se conocen infinitas familias de dígrafos no reconstruibles, incluidos los torneos (Stockmeyer [12] ) y los no torneos (Stockmeyer [13] ). Un torneo es reconstruible si no está fuertemente conectado. [14] Se ha conjeturado una versión más débil de la conjetura de reconstrucción para los dígrafos, ver la nueva conjetura de reconstrucción de dígrafos .
- Hypergraphs ( Kocay [15] ).
- Gráficos infinitos . Sea T un árbol en un número infinito de vértices tal que cada vértice tiene un grado infinito, y sea n T la unión disjunta de n copias de T. Estos gráficos son hipomórficos y, por lo tanto, no son reconstruibles. Cada subgrafo con vértice eliminado de cualquiera de estos gráficos es isomorfo: todos son la unión disjunta de un número infinito de copias de T.
- Gráficos localmente finitos. La cuestión de la reconstrucción de árboles infinitos localmente finitos (la conjetura de Harary-Schwenk-Scott de 1972) fue un problema abierto de larga data hasta 2017, cuando Bowler et al. [dieciséis]
Ver también
- Nueva conjetura de reconstrucción de dígrafos
- Simetría parcial
Otras lecturas
Para obtener más información sobre este tema, consulte la encuesta de Nash-Williams . [17]
Referencias
- ^ Kelly, PJ, un teorema de congruencia para árboles , Pacific J. Math. 7 (1957), 961–968.
- ^ Ulam, SM, Una colección de problemas matemáticos, Wiley, Nueva York, 1960.
- ^ O'Neil, Peter V. (1970). "Conjeturas de Ulam y reconstrucciones de gráficos" . Amer. Matemáticas. Mensual . 77 : 35–43. doi : 10.2307 / 2316851 .
- ^ a b Harary, F., Sobre la reconstrucción de un gráfico a partir de una colección de subgrafos. En Teoría de Gráficos y sus Aplicaciones (Proc. Sympos. Smolenice, 1963) . Publ. Casa Acad Checoslovaca. Sci., Praga, 1964, págs. 47-52.
- ^ a b c d e Pared, Nicole. "La conjetura de la reconstrucción" (PDF) . Consultado el 31 de marzo de 2014 .
- ↑ a b von Rimscha, M .: Reconstructibilidad y gráficos perfectos. Matemáticas discretas 47 , 283-291 (1983)
- ^ McKay, BD, Los gráficos pequeños son reconstruibles, Australas. J. Combin. 15 (1997), 123-126.
- ^ Bollobás, B., Casi todos los gráficos tienen la reconstrucción número tres, J. Graph Theory 14 (1990), 1-4.
- ^ a b c Harary, F. (1974), "Un estudio de la conjetura de la reconstrucción", Un estudio de la conjetura de la reconstrucción , Gráficos y Combinatoria. Lecture Notes in Mathematics , 406 , Springer, págs. 18-28, doi : 10.1007 / BFb0066431
- ^ Bondy, J.-A. (1969). "Sobre la conjetura de Ulam para gráficos separables" . Pacific J. Math . 31 : 281–288. doi : 10.2140 / pjm.1969.31.281 .
- ^ Yang Yongzhi: La conjetura de la reconstrucción es cierta si todas las gráficas conectadas a 2 son reconstruibles. Revista de teoría de grafos 12 , 237–243 (1988)
- ^ Stockmeyer, PK, La falsedad de la conjetura de reconstrucción para torneos, J. Graph Theory 1 (1977), 19-25.
- ^ Stockmeyer, PK, Un censo de dígrafos no reconstruibles, I: seis familias relacionadas, J. Combin. Teoría Ser. B 31 (1981), 232–239.
- ^ Harary, F. y Palmer, E., Sobre el problema de reconstruir un torneo a partir de sub-torneos, Monatsh. Matemáticas. 71 (1967), 14-23.
- ^ Kocay, WL, Una familia de hipergrafías no reconstruibles, J. Combin. Teoría Ser. B 42 (1987), 46–63.
- ^ Bowler, N., Erde, J., Heinig, P., Lehner, F. y Pitz, M. (2017), A contraejemplo de la conjetura de reconstrucción de árboles localmente finitos. Toro. London Math. Soc .. doi : 10.1112 / blms.12053
- ^ Nash-Williams, C. St. JA , El problema de la reconstrucción, en Temas seleccionados en la teoría de grafos , 205-236 (1978).