| Ambos lados da revisão anterior Revisão anterior Próxima revisão | Revisão anterior |
| 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 |
|---|
| 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$. | 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> |
| |
| 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$. | ---- |
| | |
| | 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> | </WRAP> |