Conjectura de reconstrução - Reconstruction conjecture

Informalmente, a conjectura de reconstrução na teoria dos grafos diz que os grafos são determinados exclusivamente por seus subgráficos. É devido a Kelly e Ulam .

Declarações formais

Um gráfico e o deck associado de subgráficos excluídos de um único vértice. Observe que algumas das cartas mostram gráficos isomórficos.

Dado um gráfico , um subgráfico excluído de um vértice de é um subgráfico formado pela exclusão de exatamente um vértice de . Por definição, é um subgrafo induzido de . ${\ displaystyle G = (V, E)}$${\ displaystyle G}$${\ displaystyle G}$${\ displaystyle G}$

Para um gráfico , o baralho de G , denotado , é o multiconjunto de classes de isomorfismo de todos os subgráficos excluídos de vértices de . Cada gráfico é chamado de cartão . Dois gráficos com o mesmo deck são considerados hipomórficos . ${\ displaystyle G}$${\ displaystyle D (G)}$${\ displaystyle G}$${\ displaystyle D (G)}$

Com essas definições, a conjectura pode ser afirmada como:

• Conjectura de reconstrução: Quaisquer dois gráficos hipomórficos em pelo menos três vértices são isomórficos.

(O requisito de que os gráficos tenham pelo menos três vértices é necessário porque ambos os gráficos em dois vértices têm os mesmos decks.)

Harary sugeriu uma versão mais forte da conjectura:

• Conjunto de conjectura de reconstrução: Quaisquer dois gráficos em pelo menos quatro vértices com os mesmos conjuntos de subgráficos excluídos de vértices são isomórficos.

Dado um gráfico , um subgráfico de borda excluída de é um subgráfico formado pela exclusão de exatamente uma borda de . ${\ displaystyle G = (V, E)}$${\ displaystyle G}$${\ displaystyle G}$

Para um gráfico , o deck de aresta de G , denotado , é o multiconjunto de todas as classes de isomorfismo de subgráficos com aresta excluída de . Cada gráfico é chamado de cartão de borda . ${\ displaystyle G}$${\ displaystyle ED (G)}$${\ displaystyle G}$${\ displaystyle ED (G)}$

• Conjectura de reconstrução de arestas: (Harary, 1964) Quaisquer dois gráficos com pelo menos quatro arestas e tendo os mesmos decks de arestas são isomórficos.

Propriedades reconhecíveis

No contexto da conjectura de reconstrução, uma propriedade de gráfico é chamada de reconhecível se for possível determinar a propriedade a partir do deck de um gráfico. As seguintes propriedades dos gráficos são reconhecíveis:

• Fim do gráfico - A fim de um gráfico , é reconhecível como o multiconjunto contém cada subgráfico criado por exclusão de um vértice . Por isso${\ displaystyle G}$${\ displaystyle | V (G) |}$${\ displaystyle D (G)}$${\ displaystyle D (G)}$${\ displaystyle G}$${\ displaystyle G}$${\ displaystyle | V (G) | = | D (G) |}$
• Número de arestas do gráfico - O número de arestas em um gráfico com vértices é reconhecível. Primeiro observe que cada aresta de ocorre em membros de . Isso é verdade pela definição de que garante que cada aresta seja incluída toda vez que cada um dos vértices com os quais está incidente for incluído em um membro de , portanto, uma aresta ocorrerá em cada membro de, exceto para os dois em que seus pontos finais são excluído. Portanto, onde é o número de arestas no i ésimo membro de .${\ displaystyle G}$${\ displaystyle n}$${\ displaystyle | E (G) |}$${\ displaystyle G}$${\ displaystyle n-2}$${\ displaystyle D (G)}$${\ displaystyle D (G)}$${\ displaystyle D (G)}$${\ displaystyle D (G)}$${\ displaystyle | E (G) | = \ sum {\ frac {q_ {i}} {n-2}}}$${\ displaystyle q_ {i}}$${\ displaystyle D (G)}$
• Sequência de graus - A sequência de graus de um gráfico é reconhecível porque o grau de cada vértice é reconhecível. Para encontrar o grau de um vértice - o vértice ausente do i ésimo membro de -, examinaremos o gráfico criado excluindo-o ,. Este gráfico contém todas as arestas não incidentes com , então se é o número de arestas em , então . Se pudermos saber o grau de cada vértice do gráfico, poderemos saber a sequência de graus do gráfico.${\ displaystyle G}$${\ displaystyle v_ {i}}$${\ displaystyle D (G)}$${\ displaystyle G_ {i}}$${\ displaystyle v_ {i}}$${\ displaystyle q_ {i}}$${\ displaystyle G_ {i}}$${\ displaystyle | E (G) | -q_ {i} = \ deg (v_ {i})}$
• (Vértice-) Conectividade - Por definição, um gráfico é -vertex-conectado ao excluir qualquer vértice cria um gráfico -vertex-conectado; portanto, se cada cartão for um gráfico conectado por vértice, sabemos que o gráfico original era um gráfico conectado por vértice. Também podemos determinar se o gráfico original estava conectado, pois isso é equivalente a ter dois dos dois sendo conectados.${\ displaystyle n}$${\ displaystyle n-1}$${\ displaystyle n-1}$${\ displaystyle n}$${\ displaystyle G_ {i}}$
• Polinômio de Tutte
• Polinômio característico
• Planaridade
• Os tipos de árvores abrangentes em um gráfico
• Polinômio cromático
• Ser um gráfico perfeito ou um gráfico de intervalo , ou certas outras subclasses de gráficos perfeitos

Verificação

Ambas as conjecturas de reconstrução e reconstrução de conjunto foram verificadas para todos os gráficos com no máximo 11 vértices por Brendan McKay .

Em um sentido probabilístico, foi demonstrado por Béla Bollobás que quase todos os gráficos são reconstrutíveis. Isso significa que a probabilidade de que um gráfico escolhido aleatoriamente nos vértices não seja reconstrutível vai para 0 quando vai para o infinito. Na verdade, foi mostrado que não apenas quase todos os gráficos são reconstrutíveis, mas também que o baralho inteiro não é necessário para reconstruí-los - quase todos os gráficos têm a propriedade de existirem três cartas em seu baralho que determinam o gráfico de maneira única. ${\ displaystyle n}$${\ displaystyle n}$

Famílias de gráficos reconstrutíveis

A conjectura foi verificada para uma série de classes infinitas de grafos (e, trivialmente, seus complementos).

• Gráficos regulares - os gráficos regulares são reconstruídos pela aplicação direta de alguns dos fatos que podem ser reconhecidos a partir do deck de um gráfico. Dado um gráfico -regular e seu baralho , podemos reconhecer que o baralho é de um gráfico regular reconhecendo sua seqüência de graus. Examinemos agora um membro da plataforma , . Este gráfico contém um certo número de vértices com grau de e vértices com grau de . Podemos adicionar um vértice a este gráfico e, em seguida, conectá-lo aos vértices de grau para criar um gráfico -regular que é isomórfico ao gráfico com o qual começamos. Portanto, todos os gráficos regulares podem ser reconstruídos a partir de seus decks. Um tipo particular de gráfico regular que é interessante é o gráfico completo.${\ displaystyle n}$${\ displaystyle G}$${\ displaystyle D (G)}$${\ displaystyle D (G)}$${\ displaystyle G_ {i}}$${\ displaystyle n}$${\ displaystyle n}$${\ displaystyle n-1}$${\ displaystyle n}$${\ displaystyle n-1}$${\ displaystyle n}$
• Arvores
• Gráficos desconectados
• Gráficos de intervalo de unidade
• Gráficos separáveis sem vértices finais
• Gráficos planares máximos
• Gráficos planares externos máximos
• Gráficos externos planares
• Bloqueios Críticos

Redução

A conjectura de reconstrução é verdadeira se todos os gráficos 2-conectados forem reconstrutíveis.

Dualidade

A conjectura de reconstrução de vértices obedece à dualidade que se pode ser reconstruída a partir de seu baralho de vértices , então seu complemento pode ser reconstruído da seguinte forma: Comece com , pegue o complemento de cada carta nele para obter , use isso para reconstruir , então pegue o complemento novamente para obter . ${\ displaystyle G}$${\ displaystyle D (G)}$${\ displaystyle G '}$${\ displaystyle D (G ')}$${\ displaystyle D (G ')}$${\ displaystyle D (G)}$${\ displaystyle G}$${\ displaystyle G '}$

A reconstrução de arestas não obedece a tal dualidade: De fato, para algumas classes de gráficos reconstrutíveis de arestas, não se sabe se seus complementos são reconstrutíveis de arestas.

Outras estruturas

Foi demonstrado que o seguinte não é em geral reconstrutível:

• Digraphs : São conhecidas famílias infinitas de digraphs não reconstrutíveis, incluindo torneios (Stockmeyer) e não torneios (Stockmeyer). Um torneio pode ser reconstruído se não estiver fortemente conectado. Uma versão mais fraca da conjectura de reconstrução foi conjecturada para dígrafos, veja nova conjectura de reconstrução de dígrafo .
• Hipergrafos ( Kocay ).
• Gráficos infinitos . Seja T uma árvore em um número infinito de vértices tal que cada vértice tenha grau infinito, e seja n T a união disjunta de n cópias de T. Esses gráficos são hipomórficos e, portanto, não podem ser reconstruídos. Cada subgrafo excluído de vértices de qualquer um desses gráficos é isomórfico: todos eles são a união disjunta de um número infinito de cópias de T.
• Grafos localmente finitos. A questão da reconstrutibilidade para árvores infinitas localmente finitas (a conjectura Harary-Schwenk-Scott de 1972) era um problema aberto de longa data até 2017, quando uma árvore não reconstrutível de grau máximo 3 foi encontrada por Bowler et al.

Veja também

• Nova conjectura de reconstrução do dígrafo
• Simetria parcial

Leitura adicional

Para obter mais informações sobre este tópico, consulte a pesquisa de Nash-Williams .

Referências