Diferenças

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

--- grafos:estruct3connect [2023/05/05 17:51] – edição externa 127.0.0.1
+++ grafos: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 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.
@@ 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.
+<wrap right>$\square$</wrap>
 </WRAP>
 -----
 <WRAP round box 100%>
@@ Linha 90: / 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.
+<wrap right>$\square$</wrap>
 </WRAP>
-----
-Teorema 3.2.3 (TUTTE 1966)
-Um grafo $G$ é $3$-conexo se, e somente se,  existe uma sequência $G_0, \dots , G_{n}$ de grafos tais que
-$(i)$ $G_0 = K^4$ e $G_{n} = G$;
-$(ii)$ $G_{i+1}$ possui uma aresta $e$ tal que $G_{i} = G_{i+1} - e$, 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, use o Lema 3.2.2 para encontrar G sucessivamente. Reciprocamente, se G é qualquer sequência de grafos satisfazendo (i) e (ii), então todos esses grafos, e em particular G, são 3-conexos pelo Lema 3.2.1
 ----
-O teorema 3.2.3 nos permite construir, recursivamente, toda a classe de grafos 3-conexos. A partir de K , 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 novo vértice de subdivisão.
+<WRAP round box 100%>
+=== Teorema: Tutte (1966) ===
-Agora nos voltamos para nosso segundo método de redução de grafos 3-conexos para K, contraindo arestas. No que segue, consideramos apenas grafos, não multigrafos.
+//Um grafo $G$ é $3$-conexo se, e somente se,  existe uma sequência $G_0, \dots , G_{n}$ de grafos tais que//
-Lema 3.2.4.
+$(i)$ $G_0 = K^4$ //e// $G_{n} = G$;
-Todo grafo 3-conexo G tem uma aresta E tal que G é novamente 3-conexo.
+$(ii)$ $G_{i+1}$ //possui uma aresta $e$ tal que $G_{i} = G_{i+1} - e$, para todo $i < n$.//
-Dem.:
-Suponha que não exista tal aresta E. Então, para cada aresta X o grafo G contém um separador S de no máximo 2 vértices. Como K, o vértice contraído V de G (consulte o capítulo 1.7) está em S e S, ou seja, G tem um vértice Z tal que V separa G. Então quaisquer dois vértices separados por V em G são separados em G por T. Como não subconjunto próprio de T separa G, cada vértice em T tem um vizinho em cada componente C de G.
-Escolhemos a aresta X, 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. Por suposição, G novamente não é 3-conexo, então novamente há um vértice Y tal que C separa G e, como antes, todo vértice em J tem um vizinho em cada componente de G.
-(FIGURAAA
-Como X e Y são adjacentes, G tem um componente D tal que D. Então todo vizinho de V em D está em C (desde C), então D e, portanto, D pela escolha de D. Isso contradiz a escolha de X, Z e C.
------
-Teorema 3.2.5 (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>
-Dem.:
+<WRAP round box 100%>
+**//Demonstração://**
-Se G é 3-conexo, então pelo Lema 3.2.4 existe uma sequência G de grafos 3-conexos satisfazendo (i) e (ii).
+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.
-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.
+<wrap right>$\square$</wrap>
+</WRAP>
------
+----
-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.)
+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.
-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.
-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 ===
-Dem.:
+  * Reinhard Diestel. [[https://www.math.uni-hamburg.de/home/diestel/books/graph.theory/preview/Ch3.pdf |“Graph Theory”]] .5th Electronic Edition 2016, pp. 62-64. Acesso em 07/05/2023.
-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.
------
+</WRAP>