Conjetura de reconstrucción

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 y Ulam.

Declaraciones formales

Un gráfico y la cubierta asociada de subgrafos de una sola versión. Nota algunas de las tarjetas muestran gráficos isomorfos.

Dado un gráfico G=()V,E){displaystyle G=(V,E)}, a subgrafo eliminado del vértice de G{displaystyle G. es un subgrafo formado por eliminar exactamente un vértice de G{displaystyle G.. Por definición, es un subgrafo inducido de G{displaystyle G..

Para un gráfico G{displaystyle G., el cubierta de G, denotado D()G){displaystyle D(G)}, es el multiconjunto de clases de isomorfismo de todos los subgrafos eliminados del vértice G{displaystyle G.. Cada gráfico en D()G){displaystyle D(G)} se llama tarjeta. Se dice que dos gráficos que tienen la misma cubierta son hipomorfo.

Con estas definiciones, la conjetura se puede establecer como:

• Conjetura de reconstrucción: Cualquier dos gráficos hipomorficos en al menos tres vértices son isomorfos.

(El requisito de que los gráficos tengan al menos tres vértices es necesario porque ambos gráficos en dos vértices tienen las mismas cubiertas.)

Harary sugirió una versión más fuerte de la conjetura:

• Conjunto de reconstrucción Conjetura: Cualquier dos gráficos en al menos cuatro vértices con los mismos conjuntos de subgrafos eliminados del vértice son isomorfos.

Dado un gráfico G=()V,E){displaystyle G=(V,E)}, un subgrafo del borde de G{displaystyle G. es un subgrafo formado por borrar exactamente un borde de G{displaystyle G..

Para un gráfico G{displaystyle G., el edge-deck of G, denotado ED()G){displaystyle ED(G)}, es el multiconjunto de todas las clases de isomorfismo de subgrafos eliminados del borde de G{displaystyle G.. Cada gráfico en ED()G){displaystyle ED(G)} se llama edge-card.

• Edge Reconstruction Conjecture: (Harario, 1964) Cualquier dos gráficos con al menos cuatro bordes y tener los mismos bordes son isomorfos.

Propiedades reconocibles

En el contexto de la conjetura de reconstrucción, una propiedad gráfica se denomina reconocible si se puede determinar la propiedad a partir de la plataforma de un gráfico. Las siguientes propiedades de los gráficos son reconocibles:

• Orden del gráfico – El orden de un gráfico G{displaystyle G., SilencioV()G)Silencio{displaystyle SilencioV(G) es reconocible desde D()G){displaystyle D(G)} como el multiset D()G){displaystyle D(G)} contiene cada subgrafo de G{displaystyle G. creado eliminando un vértice de G{displaystyle G.. Por lo tanto SilencioV()G)Silencio=SilencioD()G)Silencio{displaystyle SilencioV(G)
• Número de bordes del gráfico – El número de bordes en un gráfico G{displaystyle G. con n{displaystyle n} vertices, SilencioE()G)Silencio{displaystyle SilencioE(G) es reconocible. Primera nota que cada borde de G{displaystyle G. ocurre en n− − 2{displaystyle n-2} miembros de D()G){displaystyle D(G)}. Esto es cierto por la definición de D()G){displaystyle D(G)} que asegura que cada borde se incluye cada vez que cada uno de los vértices con los que es incidente se incluye en un miembro D()G){displaystyle D(G)}, por lo que un borde ocurrirá en cada miembro de D()G){displaystyle D(G)} excepto por los dos en los que se eliminan sus puntos finales. Por lo tanto, SilencioE()G)Silencio=.. qin− − 2{fnMicrosoft Sans Serif} {q_{i}{n-2}} {}} {cH}}} {cH}} {cH}}} {cH}}}}}}}}}} {cH}}}}}}}}}} {cH}}}}} {cH}}}}}}} {cH}}}}}}}}}}}}}}}} {}}}}} {}}}}}}} {}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}} {}}}}}}}}}} {}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}} { Donde qi{displaystyle q_{i} es el número de bordes en el imiembro de D()G){displaystyle D(G)}.
• Secuencia de grado – La secuencia de grado de un gráfico G{displaystyle G. es reconocible porque el grado de cada vértice es reconocible. Para encontrar el grado de un vértice vi{displaystyle V_{i}- el vértice ausente del imiembro de D()G){displaystyle D(G)}- examinaremos el gráfico creado por borrarlo, Gi{displaystyle G_{i}. Este gráfico contiene todos los bordes no incidentes con vi{displaystyle V_{i}Así que si qi{displaystyle q_{i} es el número de bordes en Gi{displaystyle G_{i}, entonces SilencioE()G)Silencio− − qi=deg⁡ ⁡ ()vi){displaystyle SilencioE(G) upon-q_{i}=deg(v_{i}}. Si podemos decir el grado de cada vértice en el gráfico, podemos decir la secuencia de grado del gráfico.
• (Vertex-)Connectividad – Por definición, un gráfico es n{displaystyle n}-vertex conectado al borrar cualquier vértice crea un n− − 1{displaystyle n-1}- grafito conexa; por lo tanto, si cada tarjeta es un n− − 1{displaystyle n-1}- grafito conexa, sabemos que el gráfico original era n{displaystyle n}-conexión. También podemos determinar si el gráfico original estaba conectado, ya que esto equivale a tener dos de los Gi{displaystyle G_{i} estar conectado.
• Tutte polynomial
• Polinomía característica
• Planaridad
• Los tipos de árboles azotados en un gráfico
• Chromatic polynomial
• Ser un gráfico perfecto o un gráfico de intervalos, o algunas otras subclases de gráficos perfectos

Verificación

Brendan McKay verificó las conjeturas de reconstrucción y reconstrucción de conjuntos para todos los gráficos con un máximo de 13 vértices.

En un sentido probabilístico, Béla Bollobás ha demostrado que casi todos los gráficos son reconstructibles. Esto significa que la probabilidad de que un gráfico elegido aleatoriamente en n{displaystyle n} vertices no es reconstructible va a 0 como n{displaystyle n} va al infinito. De hecho, se demostró que no sólo son casi todos los gráficos reconstructibles, pero de hecho que toda la cubierta no es necesaria para reconstruirlos, casi todos los gráficos tienen la propiedad de que existen tres cartas en su cubierta que determinan singularmente el gráfico.

Familias de grafos reconstruibles

La conjetura se ha verificado para un número infinito de clases de grafos (y, trivialmente, sus complementos).

• Gráficos regulares - Gráficos regulares son reconstructibles por aplicación directa de algunos de los hechos que pueden ser reconocidos desde la cubierta de un gráfico. Dado un n{displaystyle n}- Gráfico regular G{displaystyle G. y su cubierta D()G){displaystyle D(G)}, podemos reconocer que la cubierta es de un gráfico regular reconociendo su secuencia de grado. Examinemos ahora a un miembro de la cubierta D()G){displaystyle D(G)}, Gi{displaystyle G_{i}. Este gráfico contiene cierto número de vértices con un grado de n{displaystyle n} y n{displaystyle n} vertices con un grado de n− − 1{displaystyle n-1}. Podemos añadir un vértice a este gráfico y luego conectarlo al n{displaystyle n} vertices de grado n− − 1{displaystyle n-1} crear un n{displaystyle n}- Gráfico regular que es isomorfo al gráfico con el que empezamos. Por lo tanto, todos los gráficos regulares son reconstructibles de sus cubiertas. Un tipo particular de gráfico regular que es interesante es el gráfico completo.
• Árboles
• Gráficos desconectados
• Gráficos de intervalo de unidad
• Gráficos estables sin vértices finales
• Gráficos planificadores máximos
• Gráficos planos exteriores máximos
• Gráficos planos exteriores
• Bloques críticos

Reducción

La conjetura de reconstrucción es verdadera si todos los gráficos conectados en 2 son reconstruibles.

Dualidad

La conjetura de reconstrucción del vértice obedece la dualidad que si G{displaystyle G. puede ser reconstruido desde su cubierta de vértice D()G){displaystyle D(G)}, entonces su complemento G.{displaystyle G. puede ser reconstruido D()G.){displaystyle D(G')} como sigue: Empieza con D()G.){displaystyle D(G')}, tomar el complemento de cada tarjeta en él para conseguir D()G){displaystyle D(G)}, utilizar esto para reconstruir G{displaystyle G., luego tomar el complemento de nuevo para conseguir G.{displaystyle G..

La reconstrucción de bordes no obedece a tal dualidad: de hecho, para algunas clases de gráficos reconstruibles por bordes no se sabe si sus complementos son reconstruibles por bordes.

Otras estructuras

Se ha demostrado que los siguientes no son en general reconstruibles:

• Digraphs: Se conocen familias infinitas de digraphs no reconstructibles, incluyendo torneos (Stockmeyer) y no torneos (Stockmeyer). Un torneo es reconstructible si no está fuertemente conectado. Una versión más débil de la conjetura de reconstrucción ha sido conjeturada para digraphs, ver nueva conjetura de reconstrucción de digraph.
• Hipergrafías (Kocay).
• Gráficos infinitos. Si T es el árbol donde cada vértice tiene un grado contablemente infinito, luego la unión de dos copias disyuntivas T es hipomorfo, pero no isomorfo, a T.
• Gráficos localmente finitos, que son gráficos donde cada vértice tiene un grado finito. La cuestión de la reconstructibilidad de los árboles infinitos localmente finitos (conjetura Harary-Schwenk-Scott de 1972) fue un problema abierto de larga data hasta 2017, cuando un árbol no reconstructible de grado máximo 3 fue encontrado por Bowler et al.