Diferenças

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

--- grafos:complement [2023/03/21 22:22] – edição externa 127.0.0.1
+++ grafos:complement [2023/03/22 09:27] (atual) – edição externa 127.0.0.1
@@ Linha 54: / Linha 54: @@
 <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>