Construa o menor gráfico homeomórfico para um dado gráfico, suavizando

Question

A classe de homeomorfismo $ \mathcal{H}(G) $ de um gráfico $G$ é o conjunto de classes de isomorfismo de grafos que são topologicamente homeomórficos para $G$. É natural perguntar: Existe um "menor" representante na classe de homeomorfismo? Se sim, como encontrar? Infelizmente, não encontrei nenhum resultado útil sobre este problema após uma rápida pesquisa no Google.

No entanto, guiado pela intuição, tenho a seguinte hipótese:

O menor gráfico homeomórfico a um gráfico é obtido suavizando cada orelha máxima.

Nesta postagem, tento esboçar uma prova, mas há uma lacuna na prova, então não sei se minha hipótese está realmente correta. Eu agradeceria a qualquer pessoa por apontar meus erros e preencher a lacuna.

Aviso: esta seria uma longa postagem

Primeiro, vamos esclarecer algumas terminologias. O termo "orelha" significa coisas diferentes em diferentes livros de teoria dos grafos. Nesta postagem, adotamos a seguinte definição:

Definição 1

Uma orelha em um gráfico é:

• um ciclo cujos todos, exceto possivelmente um, vértices são de grau $2$, ou
• um caminho cujos vértices internos são de grau $2$.

Uma orelha máxima é uma orelha que não é um subgráfico adequado de uma orelha maior. Equivalentemente, um ouvido máximo é um dos seguintes:

• um ciclo que é um componente totalmente conectado por conta própria
• um ciclo em que exatamente um vértice é de grau $ \geq 3 $, enquanto todos os outros vértices são de grau $2$
• um caminho no qual todos os vértices internos são de grau $2$, enquanto ambos os vértices finais são de grau $ \neq 2 $

Duas operações comuns que preservam a topologia em gráficos são subdividir e suavizar:

Definição 2

Subdividir uma aresta significa substituí-la por uma orelha. Mais precisamente, vamos$e = uv$ ser uma vantagem.

E se $u = v$, então subdividindo o self-loop $e$ significa substituí-lo por um ciclo $C$e $u = v$ torna-se um vértice em $C$, que pode ou não ter diploma $2$, dependendo do clima $e$ está isolado.

Por outro lado, se $u \neq v$, então subdividindo $e$ significa substituí-lo por um caminho $P$e $u, v$ tornam-se os vértices finais de $P$.

Subdividir um gráfico significa realizar uma sequência de subdivisões nas bordas.

Definição 3

Alisar uma orelha significa substituí-la por uma única aresta. Mais precisamente, vamos$C$ seja um ouvido.

E se $C$ é um ciclo, então suavizando $C$ significa substituí-lo por um loop automático $e$, e o vértice do grau $ \neq 2 $ em $C$ torna-se o único incidente de vértice em $e$ (se todos os vértices estiverem $C$ são de grau $2$, basta escolher qualquer vértice).

Por outro lado, se $C$ é na verdade um caminho $P$, então alisando $P$ significa substituí-lo por uma borda sem loop $e$, e os vértices finais de $P$ tornam-se os vértices finais de $e$.

Suavizar um gráfico significa realizar uma sequência de suavização nas orelhas.

A seguir, temos o seguinte resultado clássico na topologia de gráficos:

Teorema 1

Dois gráficos são homeomórficos se e somente se um deles puder ser obtido a partir de uma seqüência de operações de subdivisão e suavização do outro.

Prova: Veja este post .

Teorema 2

Deixei $G$ e $H$ser dois gráficos homeomórficos. Então$ |V(G)| = |V(H)| $ se e apenas se $ |E(G)| = |E(H)| $.

Esboço da prova: A subdivisão (resp. Suavização) sempre aumenta (resp. Diminui) o número de vértices e arestas pelo mesmo número.$\square$

À luz do Teorema 2, podemos definir uma ordem na classe de homeomorfismo de um grafo:

Definição 4

Deixei $ \mathcal{H}(G) $ ser a classe de homeomorfismo de um gráfico $G$. Defina o pedido$\preceq$ em $ \mathcal{H}(G) $ de: $$ G_1 \preceq G_2 \iff |V(G_1)| \leq |V(G_2)| $$ para qualquer $ G_1, G_2 \in \mathcal{H}(G) $.

E se $ G_1 \preceq G_2 $ e $ G_2 \preceq G_1 $, então denotamos $ G_1 \sim G_2 $.

O pedido $\preceq$é uma pré-encomenda total, o que significa que é transitiva e quaisquer dois gráficos homeomórficos são comparáveis. Infelizmente não é um pedido total, pois$ G_1 \sim G_2 $ não implica $ G_1, G_2 $ são isomórficos, mesmo através do Teorema 2 implica $ |E(G_1)| = |E(G_2)| $.

Teorema 3

Qualquer gráfico sem vértice isolado pode ser decomposto exclusivamente em uma união de borda disjunta de orelhas máximas.

Esboço da prova:

Deixei $G$seja um gráfico sem vértice isolado. Defina a relação$R$ em $E(G)$ de: $$ eRf \iff \exists \text{ ear } C \subseteq{G} \text{ s.t. } e, f \in E(C) $$ para qualquer $ e, f \in E(G) $.

Então $R$ é uma relação de equivalência em $E(G)$, em que cada classe de equivalência contém as bordas de exatamente uma orelha máxima. Portanto,$R$ induz uma decomposição de $G$em uma união de bordas disjuntas de orelhas máximas. Por outro lado, qualquer decomposição deve ser induzida por$R$, então a decomposição é única. $\square$

Com base na decomposição acima, podemos definir o seguinte:

Definição 5

Um gráfico sem vértice isolado é chamado de liso se cada orelha máxima for de comprimento $1$. Para um gráfico$G$ sem vértice isolado, o gráfico suave obtido a partir do alisamento de cada orelha máxima em $G$ é denotado como $ \text{Smooth} (G) $.

O termo "gráfico suave" não é padrão, mas não consegui encontrar nenhum termo existente para esse gráfico, então eu o invoco sozinho.

Teorema 4

Deixei $G$ ser um gráfico suave sem vértice isolado e $ H \in \mathcal{H}(G) $, então $ G \preceq H $. Além disso,$ G \sim H $ se e apenas se $H$ é um gráfico suave.

Esboço da prova:

Pelo Teorema 1, $H$ pode ser obtido a partir de uma sequência de operações de subdivisão e suavização em $G$. Cada etapa das operações só pode mudar uma das orelhas máximas para outra orelha máxima de comprimento possivelmente diferente.

Por outro lado, em um gráfico suave, todas as orelhas máximas já têm o menor comprimento possível (ou seja, $1$), portanto, qualquer sequência de subdivisão e suavização nunca pode diminuir ainda mais o número de vértices. Portanto,$ |V(G)| \leq |V(H)| $ e a igualdade se mantém se e somente se $H$ é suave. $\square$

A seguinte afirmação é baseada na intuição, mas não sei como prová-la. É onde reside a lacuna de toda a minha prova.

Reivindicação 0

Deixei $G$ e $H$ser dois gráficos suaves sem vértice isolado. Se forem homeomórficos, então são isomórficos.

Finalmente, assumindo a afirmação acima, podemos provar a hipótese principal:

Hipótese Principal

Assuma que a reivindicação 0 está correta e deixe $G$seja um gráfico sem vértice isolado. Então$ \text{Smooth} (G) $ é o menor gráfico exclusivo em $ \mathcal{H} (G) $ com relação ao pedido $ \preceq $.

Prova:

O fato de que $ \text{Smooth} (G) \preceq H $ para todos $ H \in \mathcal{H} (G) $ segue do Teorema 4.

Para provar a exclusividade, deixe $ H \in \mathcal{H} (G) $ seja tal que $ \text{Smooth} (G) \sim H $. Desde a$ \text{Smooth} (G) $ é suave e $ H \in \mathcal{H} (\text{Smooth} (G)) $, pelo Teorema 4, $H$também é suave. A reivindicação 0, então, implica$H$ é isomórfico a $ \text{Smooth} (G) $. $\square$

Questões:

1. A reivindicação 0 está correta? Como provar isso?
2. Mesmo se a afirmação 0 estiver errada, minha hipótese principal ainda está correta?
3. Existem outros erros na minha prova?
4. Existe um termo melhor para gráficos em que cada orelha máxima é de comprimento $1$, além de "gráficos suaves"?

Answer 1

Sua prova parece correta para mim. Não vejo por que você assume que o gráfico não tem vértices isolados - isso faz diferença em algum lugar? Além disso, "gráfico suave" parece ser um nome sofisticado para um gráfico sem vértices de grau dois. (Mais precisamente, os únicos vértices de grau dois são vértices isolados com um loop.)

Vou dar uma prova de sua reivindicação. Podemos supor que os gráficos em questão estão conectados e têm pelo menos uma aresta. Para qualquer gráfico$G$, associar um gráfico colorido de vértice $Ear(G)$ Da seguinte maneira:

• Os vértices de $Ear(G)$ correspondem às orelhas na decomposição única de $G$em orelhas máximas. Eles são coloridos de azul e vermelho, dependendo se a orelha é um caminho ou um ciclo.
• Dois vértices são adjacentes se as orelhas correspondentes têm um vértice comum; se eles têm dois vértices comuns, desenhamos duas arestas paralelas. (Isso só pode acontecer se as orelhas correspondentes forem caminhos.)

Há duas observações a serem feitas que estão mais ou menos implícitas em sua prova do Teorema 4:

1. E se $G$ e $H$ são homeomórficos, então $Ear(G)$ e $Ear(H)$são isomórficos, com o isomorfismo preservando as cores do vértice. Isso segue do Teorema 1, depois de verificar que tanto a suavização quanto a subdivisão preservam$Ear(G)$.
2. E se $G$ é liso, então (desconsiderando a coloração) $Ear(G)$é apenas o gráfico de linha de$G$, definido apropriadamente para gráficos com loops e arestas múltiplas.

Convenientemente, um teorema de Whitney afirma que se os gráficos de linha de dois gráficos simples conectados são isomórficos, então os próprios gráficos são isomórficos, exceto se os gráficos forem o triângulo$K_3$ e a garra $K_{1,3}$. Observe que o triângulo não é liso. No caso de gráficos com loops e arestas paralelas, a situação é mais complicada (embora não terrivelmente, de acordo com este artigo * para o qual eu só consegui encontrar um link com acesso pago; curiosamente, o nome de Whitney está incorreto no título) , mas em nosso caso a coloração do vértice e o Teorema 4 nos fornecem informações suficientes para reconstruir o grafo original de maneira única. Você provavelmente poderia resolver isso sozinho, mas darei os detalhes para completude.

Então suponha que $G$ e $H$ são lisos e que $Ear(G)$ e $Ear(H)$são isomórficos. Primeiro, lidamos com loops: eles correspondem precisamente aos vértices vermelhos de$Ear(G)$ e $Ear(H)$. Segue-se que, se denotarmos por$G'$ e $H'$ os gráficos obtidos excluindo os loops em $G$ e $H$, então $Ear(G')$ e $Ear(H')$ são obtidos excluindo os vértices vermelhos de $Ear(G)$ e $Ear(H)$; em particular, eles são isomórficos. Agora é o suficiente para mostrar que$G'$ e $H'$ são isomórficos, uma vez que as posições dos loops são exclusivamente determinadas por $Ear(G)$: um vértice em $G'$ tem um loop se e somente se houver uma borda incidente a ele que seja adjacente a um vértice vermelho em $Ear(G)$, ou se $G'$ consiste neste único vértice (uma vez que assumimos que nossos gráficos têm pelo menos uma aresta).

Assim, podemos assumir que $G$ e $H$não contêm loops. Agora só temos que cuidar das arestas paralelas. Se duas arestas são paralelas em$G$, então por nossa construção os vértices correspondentes em $Ear(G)$são conectados por duas bordas paralelas. Mais geralmente, duas ou mais arestas paralelas em$G$ corresponde a um clique em $Ear(G)$em que cada borda é duplicada. Cada vértice em$Ear(G)$ está contido em um único máximo tal "clique duplo" (potencialmente de tamanho um), e ao contrair esses cliques e substituir arestas paralelas recém-formadas por arestas simples, obtemos o gráfico de linha do grafo simples subjacente $G$. Uma vez que isso funciona para trás também (ou seja, a partir do gráfico simples e$Ear(G)$ nós podemos recuperar $G$), podemos assumir que $G$ e $H$ são simples.

Então terminamos pelo teorema de Whitney, certo? Bem, não tão rápido. Pode acontecer que depois de deixar loops e bordas paralelas de$G$ e $H$, ficamos com um triângulo e $K_{1,3}$: afinal, um triângulo com arestas duplas é liso. Mas isso é descartado pelo Teorema 4: o original$G$ e $H$tinha o mesmo número de vértices, e deixar arestas não muda isso. assim$G$ e $H$ são realmente isomórficos.

^{* Note que, pelo que eu posso dizer, a noção de gráfico de linha usada no artigo é diferente da usada aqui, em que os vértices correspondentes às arestas paralelas ainda estão conectados com apenas uma aresta.}