Diferenças

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

--- grafos:estruct3connected [2023/05/07 16:03] – edição externa 127.0.0.1
+++ grafos:estruct3connected [2023/05/07 17:04] (atual) – edição externa 127.0.0.1
@@ Linha 1: / Linha 1: @@
-==== A estrutura de grafos $3$-conexo em geral ====
+==== A estrutura de grafos $3$-conexo: sem multigrafos ====
 Agora nos voltamos para nosso segundo método de redução de grafos $3$-conexos para $K^4$, contraindo arestas. No que segue, consideramos apenas grafos, não multigrafos.
@@ Linha 15: / Linha 15: @@
 Escolhemos a aresta $xy$, o vértice $z$ e a componente $C$ de modo que $|C|$ seja o menor possível, e escolhemos um vizinho $v$ de $z$ em $C$.
-{{ :grafos:graph300.png?400 |}}
+{{ :grafos:graph300.png?450 |}}
 Por suposição, $G/zv$ novamente não é $3$-conexo, então novamente há um vértice $w$ tal que $\{z,v,w\}$ separa $G$ e, como antes, todo vértice em $\{z,v,w\}$ tem um vizinho em cada componente de $G-\{z,v,w\}$.
@@ 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$.
+<wrap right>$\square$</wrap>
 </WRAP>
+-----
+<WRAP round box 100%>
+=== Teorema: Tutte(1961) ===
+//Um grafo $G$ é $3$-conexo se, e somente se, existe uma sequência $G_0, \dots ,G_{n}$ de grafos com as duas seguintes propriedades://
+$(i)$ //$G_0 = K^4$ e $G_{n} = G$;//
+$(ii)$ //$G_{i+1}$ possui uma aresta $xy$ tal que $d(x),d(y) \geq 3$ e $G_{i} = G_{i+1}/xy$, para todo $i<n$.//
+//Além disso, os grafos de qualquer uma dessas sequências são todos $3$-conexos.//
+</WRAP>
+<WRAP round box 100%>
+**//Demonstração://**
+Se $G$ é $3$-conexo, então pelo Lema $1$ acima existe uma sequência $G_{n}, \dots, G_0$ de grafos $3$-conexos satisfazendo $(i)$ e $(ii)$.
+Inversamente, e para mostrar o enunciado final do teorema , seja $G_0, \dots G_{n}$ uma sequência de grafos satisfazendo $(i)$ e $(ii)$; mostramos que se $G_{i}$ é $3$-conexo, $G_{i+1}$ também é para todo $i<n$. Suponha que não, seja $S$ um separador de no máximo $2$ vértices em $G_{i+1}$, e seja $C_1,C_2$ duas componentes de $G_{i+1}-S$ . Como $x$ e $y$ são adjacentes, podemos supor que $\{x,y\} \cap V(C_1) = \emptyset$.
+{{ :grafos:graph301.png?400 |}}
+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>
 -----
-Teorema 3.2.5 (TUTTE 1961)
+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.)
-Um grafo $G$ é $3$-conexo se, e somente se, existe uma sequência $G_0, \dots ,G_{n}$ de grafos com as duas seguintes propriedades:
+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.
-$(i)$ $G_0 = K^4$ e $G_{n} = G$;
-$(ii)$ G_{i+1} possui uma aresta $xy$ tal que $d(x),d(y) \geq 3$ e $G_{i} = G_{i+1}/xy$, para todo i <n.
-Além disso, os grafos de qualquer uma dessas sequências são todos $3$-conexos.
-Dem.:
-Se G é 3-conexo, então pelo Lema 3.2.4 existe uma sequência G de grafos 3-conexos satisfazendo (i) e (ii).
-Inversamente, e para mostrar o enunciado final do teorema , seja G uma sequência de grafos satisfazendo (i) e (ii); mostramos que se G é 3-conexo, G também é para todo I. Suponha que não, seja S um separador de no máximo 2 vértices em G e seja C dois componentes de G . Como X e Y são adjacentes, podemos supor que V. Então C não contém ambos os vértices X nem um vértice V: caso contrário, V ou V estariam separados de C em G por no máximo dois vértices, uma contradição. Mas agora C contém apenas um vértice: X ou Y. Isso contradiz nossa suposição de D.
 -----
-Assim como o Teorema 3.2.3, o Teorema 3.2.5 nos permite construir todos os grafos 3-conexos indutivamente a partir de K, 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; 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 gráficos da forma C são chamados de rodas; assim, K é a menor roda.)
+<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.
-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.
+</WRAP>
-Teo 3.2.6 (TUTTE 1963)
-O espaço de ciclo de um grafo 3-conexo é gerado por seus ciclos induzidos não separados.
-Dem.:
-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.
------