grafos:estruct3connect

Diferenças

Aqui você vê as diferenças entre duas revisões dessa página.

Link para esta página de comparações

Ambos lados da revisão anterior Revisão anterior
Próxima revisão		 Revisão anterior
grafos:estruct3connect [2023/05/07 15:32] – edição externa 127.0.0.1grafos:estruct3connect [2023/05/07 17:03] (atual) – edição externa 127.0.0.1
Linha 1: Linha 1:
-==== A estrutura de um grafo $3$-conexo a partir de um $K^4$ ====+==== A estrutura de um grafo $3$-conexo a partir de um $K^4$: com multigrafos ====
  
 Nesta seção, descrevemos como todo grafo $3$-conexo pode ser obtido de um $K^4$ por uma sucessão de operações elementares preservando a $3$-conexidade. Provamos então um teorema de Tutte sobre a estrutura algébrica do espaço cíclico de grafos $3$-conexos. Nesta seção, descrevemos como todo grafo $3$-conexo pode ser obtido de um $K^4$ por uma sucessão de operações elementares preservando a $3$-conexidade. Provamos então um teorema de Tutte sobre a estrutura algébrica do espaço cíclico de grafos $3$-conexos.
Linha 24: Linha 24:
 Pensando em $G$ como obtido de $G \dot -e$ adicionando $e$, chamemos os vértices de $G \dot -e$ de vértices //antigos// de $G$, e qualquer outro vértice de $G$ (que será um fim de $e$) de novo vértice //novo//. Lembrando que $G \dot -e$, sendo $3$-conexo, não possui arestas paralelas, é fácil ver que, em $G$, não há dois vértices $x_1,x_2$ que possam separar um novo vértice de todos os vértices antigos. Portanto, basta mostrar que $\{x_1,x_2\}$ não pode separar dois vértices antigos. Se o fizessem, esses vértices antigos seriam separados em $G \dot -e$  por $x_1'$ e $x_2'$, onde $x_{i}' = x_{i}$  ou, se $x_{i}$ for novo, $x_{i}'$ é a aresta de $G \dot -e$ subdividida por $x_{i}$. Pelo [[.cicloDeltaKConexidade| Teorema]], isso contradiz nossa suposição de que $G \dot -e$ é $3$-conexo. Pensando em $G$ como obtido de $G \dot -e$ adicionando $e$, chamemos os vértices de $G \dot -e$ de vértices //antigos// de $G$, e qualquer outro vértice de $G$ (que será um fim de $e$) de novo vértice //novo//. Lembrando que $G \dot -e$, sendo $3$-conexo, não possui arestas paralelas, é fácil ver que, em $G$, não há dois vértices $x_1,x_2$ que possam separar um novo vértice de todos os vértices antigos. Portanto, basta mostrar que $\{x_1,x_2\}$ não pode separar dois vértices antigos. Se o fizessem, esses vértices antigos seriam separados em $G \dot -e$  por $x_1'$ e $x_2'$, onde $x_{i}' = x_{i}$  ou, se $x_{i}$ for novo, $x_{i}'$ é a aresta de $G \dot -e$ subdividida por $x_{i}$. Pelo [[.cicloDeltaKConexidade| Teorema]], isso contradiz nossa suposição de que $G \dot -e$ é $3$-conexo.
  
 +<wrap right>$\square$</wrap>
 </WRAP> </WRAP>
  
Linha 45: Linha 46:
  
 Portanto $P$ satisfaz $(*)$. Suprimindo quaisquer vértices de grau $2$ em $H \cup P$ obtemos um multigrafo $J'$ tal que $J' \dot -e =J$, onde $e$ é a aresta correspondente a $P$. Por $(*)$ a aresta $e$ não é paralela a uma aresta de $J$, então $J'$ é de fato um grafo. Pelo Lema $1$ acima, $J'$ é $3$-conexo. Logo, $J' \backsimeq G$ pela maximalidade de $J$, completando a prova. Portanto $P$ satisfaz $(*)$. Suprimindo quaisquer vértices de grau $2$ em $H \cup P$ obtemos um multigrafo $J'$ tal que $J' \dot -e =J$, onde $e$ é a aresta correspondente a $P$. Por $(*)$ a aresta $e$ não é paralela a uma aresta de $J$, então $J'$ é de fato um grafo. Pelo Lema $1$ acima, $J'$ é $3$-conexo. Logo, $J' \backsimeq G$ pela maximalidade de $J$, completando a prova.
 +
 +<wrap right>$\square$</wrap>
 </WRAP> </WRAP>
  
Linha 66: Linha 69:
 Se $G$ é $3$-conexo, use o Lema $2$ acima para encontrar $G_{n} \dots , G_0$ sucessivamente. Reciprocamente, se $G_0 \dots G_{n}$ é qualquer sequência de grafos satisfazendo $(i)$ e $(ii)$, então todos esses grafos, e em particular $G = G_{n}$, são $3$-conexos pelo Lema $1$ acima. Se $G$ é $3$-conexo, use o Lema $2$ acima para encontrar $G_{n} \dots , G_0$ sucessivamente. Reciprocamente, se $G_0 \dots G_{n}$ é qualquer sequência de grafos satisfazendo $(i)$ e $(ii)$, então todos esses grafos, e em particular $G = G_{n}$, são $3$-conexos pelo Lema $1$ acima.
  
 +<wrap right>$\square$</wrap>
 </WRAP> </WRAP>
 +
 +----
 +
 +O teorema logo acima nos permite construir, recursivamente, toda a classe de grafos $3$-conexos. A partir de $K^4$ , simplesmente adicionamos a cada grafo já construído uma nova aresta em todos os sentidos compatíveis com $(ii)$: entre dois vértices já existentes, entre novos vértices subdivididos inseridos (não na mesma aresta), ou entre um vértice antigo e um vértice novo de subdivisão.
 +
  
 ---- ----
  • grafos/estruct3connect.1683484369.txt.gz
  • Última modificação: 2023/05/07 15:32
  • por 127.0.0.1