Diferenças

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

--- grafos:complement [2023/03/21 20:47] – edição externa 127.0.0.1
+++ grafos:complement [2023/03/22 09:27] (atual) – edição externa 127.0.0.1
@@ Linha 21: / Linha 21: @@
 <WRAP round box 100%>
-//**Demonstração:**//
+//**Demonstração:**// Observe primeiro que a última afirmação do teorema decorre imediatamente das afirmações $(i)$ e $(ii)$: se $G$ tem um $1$-fator, temos $q(G-S) \leq |S|$ e, portanto, $|S| = |\mathcal{C}_{G-S}|$ como acima; caso contrário, se $|S| = |\mathcal{C}_{G-S}|$ , então a existência de um  $1$-fator segue diretamente de $(i)$ e $(ii)$.
+Provamos agora a existência de um conjunto $S$ satisfazendo $(i)$ e $(ii)$, por indução em $|G|$. Para $|G|=0$ podemos tomar $S = \emptyset$. Agora seja $G$ dado por $|G| > 0$, e assuma que a afirmação vale para grafos com menos vértices.
+Considere os conjuntos $T \subseteq V$ para os quais a condição de Tutte falha, ou seja, para qual
+$$d(T) := d_{G}(T):= q(G-T)-|T|$$
+é máximo, e seja $S$ o maior desses conjuntos $T$. Observe que $d(S) \geq d(\emptyset) \geq 0$.
+Primeiro mostramos que toda componente $C \in \mathcal{C}_{G-S} =: \mathcal{C}$ é ímpar. Se $|C|$ é par, escolha um vértice $c \in C$ e considere $T := S \cup \{c\}$. Como $C-c$ tem ordem ímpar, ele tem pelo menos um componente ímpar, que também é um componente de $G-T$. Portanto, enquanto $|T| = |S|+1$,
+$$q(G-T) \geq q(G-S)+1$$
+então, $d(T) \geq d(S)$ contradizendo a escolha de $S$.
+Em seguida, provamos a afirmação $(ii)$, de que todo $C \in \mathcal{C}$ é um fator-crítico. Suponha que existam $C \in \mathcal{C}$ e $c \in C$ tais que $C' := C-c$ não tenha $1$-fator. Pela hipótese de indução (e pelo fato de que, como mostrado anteriormente, para $G$ fixo nosso teorema implica o teorema de Tutte) existe um conjunto $S' \subseteq V(C')$ com
+$$q(C'-S') > |S'|.$$
+Como $|C|$ é ímpar e, portanto, $|C'|$ é par, os números $q(C'-S')$ e $|S'|$ são ambos pares ou ambos ímpares, então eles não podem diferir por exatamente $1$. Podemos, portanto, aguçar a desigualdade acima para:
+$$q(C'-S') \geq |S'|+2,$$
+nos dando $d_{C'}(S') \geq 2$. Então para $T := S \cup \{c\} \cup S'$, temos
+$$d(T) \geq d(S)-1-1 + d_{C'}(S') \geq d(S),$$
+onde o primeiro $'-1'$ vem da perda de $C$ como um componente ímpar e o segundo vem da inclusão de $c$ no conjunto $T$. Como antes, isso contradiz a escolha de $S$.
+Resta mostrar que $S$ é compatível(emparelhável) com $\mathcal{C}_{G-S}$. Caso contrário, pelo teorema do casamento existe um conjunto $S' \subseteq S$ que envia arestas para menos que $|S'|$ componentes em $\mathcal{C}$. Como os outros componentes em $\mathcal{C}$ também são componentes de $G-(S \setminus S')$, o conjunto $T = S \setminus S'$ satisfaz $d(T) > d(S)$, contrária à escolha de $S$.
+<wrap right>$\square$</wrap>
+</WRAP>
+----
+Vamos considerar mais uma vez o conjunto $S$ do teorema acima, juntamente com qualquer emparelhamento $M$ em $G$. Como antes, escrevemos $\mathcal{C} : = \mathcal{C}_{G-S}$. Vamos denotar por $k_{S}$ o número de arestas em $M$ com pelo menos uma extremidade em $S$, e por $k_{\mathcal{C}}$ o número de arestas em $M$ com ambas as extremidades em $G-S$.
+Como cada $C \in \mathcal{C}$ é ímpar, pelo menos um de seus vértices não é incidente com uma aresta do segundo tipo. Portanto, todo emparelhamento $M$ satisfaz
+$$k_{S} \leq |S|,$$
+e
+$$k_{C} \leq \frac{1}{2} (|V| - |S| -|\mathcal{C}|). (*)$$
+Além disso, $G$ contém um emparelhamento $M_0$ com igualdade em ambos os casos: primeiro escolha $|S|$ arestas entre $S$ e $\bigcup \mathcal{C}$  de acordo com $(i)$, e então use $(ii)$ para encontrar um conjunto adequado de $\frac{1}{2}(|C|-1)$ arestas em cada componente $C \in \mathcal{C}$. Este emparelhamento $M_0$, portanto, possui exatamente
+$$|M_0| = |S| + \frac{1}{2}(|V|-|S|-|\mathcal{C}|). (**)$$
+arestas.
+Agora $(*)$ e $(**)$ juntos implicam que todo emparelhamento $M$ de máxima cardinalidade satisfaz ambas as partes de $(*)$ com igualdade: por $|M| \geq |M_0|$ e $(**)$, $M$ tem pelo menos $|S| + \frac{1}{2}(|V|-|S|-|\mathcal{C}|)$ arestas, o que implica por $(*)$ que nenhuma das desigualdades em $(*)$ pode ser estrita.
+Mas a igualdade em $(*)$, por sua vez, implica que $M$ tem a estrutura descrita acima: por $k_{S} = |S|$, todo vértice $s \in S$ é o fim de uma aresta $st \in M$ com $t \in G-S$, e por $k_{\mathcal{C}} = \frac{1}{2}(|V|-|S|-|\mathcal{C}|)$ exatamente $\frac{1}{2}(|C|-1)$ arestas de $M$ estão em $C$, para cada $C \in \mathcal{C}$. Finalmente, uma vez que estas últimas arestas perdem apenas um vértice em cada $C$ , as extremidades $t$ das arestas $st$ acima encontram-se em diferentes componentes $C$ para diferentes $s$.
+O teorema aparentemente técnico, portanto, esconde uma riqueza de informações estruturais: ele contém a essência de uma descrição detalhada de todas os emparelhamento de máxima cardinalidade em todos os grafos.
+----
+<WRAP round info>
+=== Referências ===
+  * Reinhard Diestel. [[https://www.math.uni-hamburg.de/home/diestel/books/graph.theory/preview/Ch2.pdf|“Graph Theory”]] .5th Electronic Edition 2016, pp. 45. Acesso em 21/03/2023.
 </WRAP>