Conjetura de reconstrucción

En teoría de grafos , informalmente, la conjetura de reconstrucción afirma que los grafos están determinados de forma única por sus subgrafos. Se debe a Kelly ^{[ 1 ]} y Ulam . ^{[ 2 ] [ 3 ]}

Dado un gráfico${\displaystyle G=(V,E)}$, un subgrafo con vértices eliminados de${\displaystyle G}$es un subgrafo formado al eliminar exactamente un vértice de${\displaystyle G}$. Por definición, es un subgrafo inducido de${\displaystyle G}$.

Para un gráfico${\displaystyle G}$, la baraja de G , denotada${\displaystyle D(G)}$, es el multiconjunto de clases de isomorfismo de todos los subgrafos con vértices eliminados de${\displaystyle G}$Cada gráfico en${\displaystyle D(G)}$se llama carta . Se dice que dos gráficos que tienen la misma baraja son hipomórficos .

Con estas definiciones, la conjetura puede enunciarse de la siguiente manera:

• Conjetura de reconstrucción: Cualquier par de grafos hipomórficos con al menos tres vértices son isomorfos.

(El requisito de que los grafos tengan al menos tres vértices es necesario porque ambos grafos con 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 grafos cualesquiera con al menos cuatro vértices que tengan los mismos conjuntos de subgrafos con vértices eliminados son isomorfos.

Dado un gráfico${\displaystyle G=(V,E)}$, un subgrafo con aristas eliminadas de${\displaystyle G}$es un subgrafo formado al eliminar exactamente una arista de${\displaystyle G}$.

Para un gráfico${\displaystyle G}$, el mazo de aristas de G , denotado${\displaystyle ED(G)}$, es el multiconjunto de todas las clases de isomorfismo de subgrafos con aristas eliminadas de${\displaystyle G}$Cada gráfico en${\displaystyle ED(G)}$se denomina tarjeta de borde .

• Conjetura de reconstrucción de aristas: (Harary, 1964) ^{[ 4 ]} Cualquier par de grafos con al menos cuatro aristas y que tengan los mismos conjuntos de aristas son isomorfos.

En el contexto de la conjetura de reconstrucción, una propiedad de un grafo se denomina reconocible si se puede determinar a partir de la estructura básica del grafo. Las siguientes propiedades de los grafos son reconocibles:

• Orden del gráfico – El orden de un gráfico${\displaystyle G}$,${\displaystyle |V(G)|}$es reconocible por${\displaystyle D(G)}$como el multiconjunto${\displaystyle D(G)}$contiene cada subgrafo de${\displaystyle G}$creado al eliminar un vértice de${\displaystyle G}$. Por eso${\displaystyle |V(G)|=|D(G)|}$^{[ 5 ]}
• Número de aristas del grafo : el número de aristas en un grafo.${\displaystyle G}$con${\displaystyle n}$vértices,${\displaystyle |E(G)|}$es reconocible. Primero observe que cada borde de${\displaystyle G}$ocurre en${\displaystyle n-2}$miembros de${\displaystyle D(G)}$Esto es cierto por definición de${\displaystyle D(G)}$lo que garantiza que cada arista se incluya cada vez que cada uno de los vértices con los que incide se incluya en un miembro de${\displaystyle D(G)}$, por lo que aparecerá una arista en cada miembro de${\displaystyle D(G)}$excepto en los dos en los que se eliminan sus puntos finales. Por lo tanto,${\displaystyle |E(G)|=\sum {\frac {q_{i}}{n-2}}}$dónde${\displaystyle q_{i}}$es el número de aristas en el i -ésimo miembro de${\displaystyle D(G)}$. ^{[ 5 ]}
• Número de subgrafos de orden${\displaystyle k<n}$(Lema de Kelly) - Generalizando la estrategia de conteo de aristas, podemos decir que para algún subgrafo${\displaystyle H}$con${\displaystyle k}$vértices en${\displaystyle G}$con${\displaystyle n}$vértices, el número de veces${\displaystyle H}$aparece en${\displaystyle G}$(conocido como${\displaystyle {\binom {G}{H}}}$) es reconstruible. Como cada instancia de${\displaystyle H}$en G aparecerá en exactamente todas las cartas en las que un vértice de${\displaystyle H}$no se elimina, cada instancia distinta de${\displaystyle H}$aparecerá en${\displaystyle n-k}$tarjetas. Como tal,${\displaystyle {\binom {G}{H}}=\sum {\frac {\binom {D_{i}}{H}}{n-k}}}$, dónde${\displaystyle D_{i}}$es el${\displaystyle i}$tarjeta. ^{[ 5 ]}
• Secuencia de grados : la secuencia de grados de un grafo.${\displaystyle G}$es reconocible porque el grado de cada vértice es reconocible. Para hallar el grado de un vértice${\displaystyle v_{i}}$—el vértice ausente del i- ésimo miembro de${\displaystyle D(G)}$—, examinaremos el gráfico creado al eliminarlo,${\displaystyle G_{i}}$Este gráfico contiene todas las aristas no incidentes con${\displaystyle v_{i}}$, entonces si${\displaystyle q_{i}}$es el número de aristas en${\displaystyle G_{i}}$, entonces${\displaystyle |E(G)|-q_{i}=\deg(v_{i})}$Si podemos determinar el grado de cada vértice del grafo, podemos determinar la secuencia de grados del grafo. ^{[ 5 ]}
• Conectividad (de vértices) – Por definición, un grafo es${\displaystyle n}$-vertex-connected al eliminar cualquier vértice crea un${\displaystyle n-1}$-grafo conectado por vértices; por lo tanto, si cada tarjeta es un${\displaystyle n-1}$-grafo conectado por vértices, sabemos que el grafo original era${\displaystyle n}$-conexo-vértice. También podemos determinar si el grafo original era conexo, ya que esto es equivalente a tener dos cualesquiera de los vértices.${\displaystyle G_{i}}$estar conectado. ^{[ 5 ]}
• polinomio de Tutte
• Polinomio característico
• Planitud
• El número de árboles de expansión en un grafo
• polinomio cromático
• Ser un grafo perfecto o un grafo de intervalos , o ciertas otras subclases de grafos perfectos ^{[ 6 ]}

Tanto la conjetura de reconstrucción como la de reconstrucción de conjuntos han sido verificadas para todos los grafos con como máximo 13 vértices por Brendan McKay . ^{[ 7 ] [ 8 ]}

En un sentido probabilístico, Béla Bollobás ha demostrado que casi todos los grafos son reconstruibles. ^{[ 9 ]} Esto significa que la probabilidad de que un grafo elegido al azar en${\displaystyle n}$vértices no es reconstruible va a 0 como${\displaystyle n}$va hasta el infinito. De hecho, se demostró que no solo casi todos los grafos son reconstruibles, sino que ni siquiera es necesario tener toda la baraja para reconstruirlos : casi todos los grafos tienen la propiedad de que existen tres cartas en su baraja que determinan de forma única el grafo.

La conjetura de reconstrucción es verdadera si todos los grafos 2-conexos son reconstruibles. ^{[ 12 ]}

La conjetura de reconstrucción de vértices obedece a la dualidad de que si${\displaystyle G}$puede reconstruirse a partir de su conjunto de vértices${\displaystyle D(G)}$, luego su complemento${\displaystyle G'}$puede reconstruirse a partir de${\displaystyle D(G')}$de la siguiente manera: Comience con${\displaystyle D(G')}$, toma el complemento de cada carta en ella para obtener${\displaystyle D(G)}$, utilice esto para reconstruir${\displaystyle G}$, luego toma el complemento nuevamente para obtener${\displaystyle G'}$.

La reconstrucción de aristas no obedece a ninguna dualidad de este tipo: de hecho, para algunas clases de grafos reconstruibles mediante aristas, se desconoce si sus complementos son reconstruibles mediante aristas.

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

• Digrafos : Se conocen familias infinitas de digrafos no reconstruibles, incluyendo torneos (Stockmeyer ^{[ 13 ]} ) y no-torneos (Stockmeyer ^{[ 14 ]} ). Un torneo es reconstruible si no es fuertemente conexo. ^{[ 15 ]} Se ha conjeturado una versión más débil de la conjetura de reconstrucción para digrafos, véase la nueva conjetura de reconstrucción de digrafos .
• Hipergrafos , incluyendo todos los hipergrafos k-uniformes para k>2 ( Kocay ^{[ 16 ]} ).
• Grafos infinitos . Si T es el árbol donde cada vértice tiene un grado infinito numerable , entonces la unión de dos copias disjuntas de T es hipomorfa, pero no isomorfa, a T. ( Fisher ^{[ 17 ]} ) ^{[ 18 ] [ 19 ]}
• Los grafos localmente finitos son grafos donde cada vértice tiene grado finito. La cuestión de la reconstructibilidad de los á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. encontraron un árbol no reconstruible de grado máximo 3 ^{[ 20 ] .}

• Nueva conjetura sobre la reconstrucción de digrafos
• Simetría parcial

Para obtener más información sobre este tema, consulte la encuesta de Nash-Williams . ^{[ 21 ]}