grafos:estruct3connected

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:estruct3connected [2023/05/07 16:22] – pivagrafos:estruct3connected [2023/05/07 17:04] (atual) – edição externa 127.0.0.1
Linha 21: Linha 21:
 Como $x$ e $y$ são adjacentes, $G-\{z,v,w\}$ tem um componente $D$ tal que $D \cap \{x,y\} = \emptyset$. Então todo vizinho de $v$ em $D$ está em $C$ (desde que $v \in C$), então $D \cap C = \emptyset$ e, portanto, $D \subsetneq C$ pela escolha de $D$. Isso contradiz a escolha de $xy,z$ e $C$. Como $x$ e $y$ são adjacentes, $G-\{z,v,w\}$ tem um componente $D$ tal que $D \cap \{x,y\} = \emptyset$. Então todo vizinho de $v$ em $D$ está em $C$ (desde que $v \in C$), então $D \cap C = \emptyset$ e, portanto, $D \subsetneq C$ pela escolha de $D$. Isso contradiz a escolha de $xy,z$ e $C$.
  
 +<wrap right>$\square$</wrap>
 </WRAP> </WRAP>
  
Linha 46: Linha 47:
 Então $C_2$ não contém ambos os vértices $x,y$ nem um vértice $v \notin \{x,y\}$: caso contrário, $v_{xy}$ ou $v$ estariam separados de $C_1$ em $G_{i}$ por no máximo dois vértices, uma contradição. Mas agora $C_2$ contém apenas um vértice: $x$ ou $y$. Isso contradiz nossa suposição de que $d(x),d(y) \geq 3$. Então $C_2$ não contém ambos os vértices $x,y$ nem um vértice $v \notin \{x,y\}$: caso contrário, $v_{xy}$ ou $v$ estariam separados de $C_1$ em $G_{i}$ por no máximo dois vértices, uma contradição. Mas agora $C_2$ contém apenas um vértice: $x$ ou $y$. Isso contradiz nossa suposição de que $d(x),d(y) \geq 3$.
  
 +<wrap right>$\square$</wrap>
 </WRAP> </WRAP>
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
  
 ----- -----
Linha 82: Linha 54:
 Assim como o [[grafos:estruct3connect#teorematutte_1966 |Teorema]], o Teorema acima nos permite construir todos os grafos $3$-conexos indutivamente a partir de $K^4$, por simples alterações locais e sem jamais sair da classe dos grafos $3$-conexos. Dado um grafo $3$-conexo já construído, escolha qualquer vértice $v$ e divida-o em dois vértices adjacentes $v',v''$. Em seguida, junte-os a todos os antigos vizinhos de $v$, cada um a pelo menos dois. Este é o núcleo essencial de um resultado de Tutte conhecido como **//Teorema da roda//**. ( Os grafos da forma $C^{n} * K^1$ são chamados de **rodas**; assim, $K^4$ é a menor roda.) Assim como o [[grafos:estruct3connect#teorematutte_1966 |Teorema]], o Teorema acima nos permite construir todos os grafos $3$-conexos indutivamente a partir de $K^4$, por simples alterações locais e sem jamais sair da classe dos grafos $3$-conexos. Dado um grafo $3$-conexo já construído, escolha qualquer vértice $v$ e divida-o em dois vértices adjacentes $v',v''$. Em seguida, junte-os a todos os antigos vizinhos de $v$, cada um a pelo menos dois. Este é o núcleo essencial de um resultado de Tutte conhecido como **//Teorema da roda//**. ( Os grafos da forma $C^{n} * K^1$ são chamados de **rodas**; assim, $K^4$ é a menor roda.)
  
-Para inteiros maiores K não é mais verdade que em qualquer grafo k-conexo podemos contrair uma aresta de modo a obter outro grafo k-conexo. No entanto, para todo K existe uma constante N tal que em todo grafo k-conexo podemos excluir ou contrair uma aresta de modo que o grafo resultante não tenha separação de ordem menor que K em que ambos os lados tenham pelo menos N vértices. Veja as notas.+Para inteiros maiores $k$ não é mais verdade que em qualquer grafo $k$-conexo podemos contrair uma aresta de modo a obter outro grafo $k$-conexo. No entanto, para todo $k$ existe uma constante $n_{k}$ tal que em todo grafo $k$-conexo podemos excluir ou contrair uma aresta de modo que o grafo resultante não tenha separação de ordem menor que $k$ em que ambos os lados tenham pelo menos $n_{k}$ vértices.
  
-Teo 3.2.6 (TUTTE 1963)+-----
  
-O espaço de ciclo de um grafo 3-conexo é gerado por seus ciclos induzidos não separados.+<WRAP round info> 
 +=== Referências === 
 +  * Reinhard Diestel. [[https://www.math.uni-hamburg.de/home/diestel/books/graph.theory/preview/Ch3.pdf |“Graph Theory”]] .5th Electronic Edition 2016, pp. 64-65. Acesso em 07/05/2023.
  
-Dem.: +</WRAP>
- +
-Seja G um grafo fixo 3-conexo, de ordem N digamos. Provamos que cada um de seus ciclos C é uma soma de ciclos induzidos não separados, aplicando indução em K, onde B denota a maior ordem de um componente de G se houver um, e B se V. +
- +
-Não há ciclos C para os quais K, então a indução começa. Agora seja dado C para a etapa de indução. Se C é um ciclo de extensão, é a soma de dois ciclos C, onde E uma corda. Como K, estamos em casa por indução. +
- +
-Suponha agora que G, e seja o maior componente de G. Suponha primeiro que  +
- +
-G contém um caminho C P tal que cada um dos dois caminhos U em C tem um vértice interno em N. (*) +
-(FIGURAAAAA +
- +
-Então C é a soma dos dois ciclos C contendo P, e para cada um destes C existe uma componente de G que contém B propriamente. Daí K , e estamos novamente em casa por indução. +
- +
-Suponha finalmente que (*) falhe. Então cada vértice de C envia uma aresta para B. (De fato, se não, então C contém um N-caminho Q com T. Como G é 3-conexo, C, e há um caminho Q em G. Tal caminho P seria satisfaz (*).) Como V, qualquer acorde de C também seria um caminho P como em (*), então C não tem acorde. Portanto, a menos que o próprio C seja induzido e não separe, G tem um componente B. Seja P um caminho C através de B, e seja Q um caminho C-P em G. Observe que Q também evita B. Agora C contém três ciclos C somando a C e cada um perdendo um vértice de C. Como todo vértice de C envia uma aresta para B, portanto, temos K para cada K, completando a etapa de indução. +
- +
------+
  • grafos/estruct3connected.1683487356.txt.gz
  • Última modificação: 2023/05/07 16:22
  • por piva