grafos:konigtheorem [WikiMat]

Essa página está em modo somente de leitura. Você pode visualizar a fonte, mas não alterá-la. Informe-se com o administrador do Wiki, caso você ache que isso está incorreto.
==== Teorema de Emparelhamento de König ====

O seguinte teorema caracteriza a cardinalidade máxima de um emparelhamento em um grafo por um tipo de condição de dualidade.

<WRAP round box 100%> 
=== Teorema de Emparelhamento de König ===
A maior cardinalidade de um [[.matching | emparelhamento]] num grafo [[defbipartite | bipartido]] $G$ é a menor cardinalidade de um conjunto de vértices que 
cobre as arestas.
</WRAP>

<WRAP round box 100%>
//**Demonstração:**//

Considere um grafo $G=(V,E)$ bipartido, com bipartição $\{A,B\}$. Seja $M$ um emparelhamento de $G$ de máxima cardinalidade. Para toda aresta de $M$, escolheremos uma de suas extremidades: o vértice em $B$, se existe um [[.camaltern | caminho alternante]] que termina ali, e caso contrário, escolhemos seu vértice em $A$. Chamaremos o conjunto desses vértices de $U$.

{{ :grafos:part2.png?300 |}}

Perceba que qualquer conjunto de vértices que cobre $E$ deve também cobrir $M$, ou seja, a cardinalidade mínima de tal conjunto é $|M|$. Como $|U|=|M|$, basta mostrar que $U$ cobre $E$. Observe, também, que se algum caminho alternante termina em $b\in B$, então $b\in U$, pois caso contrário teríamos um [[matching_alternatingpaths | caminho ampliador]], contrariando a hipótese que $M$ é de tamanho máximo.

Com $a\in A$ e $b\in B$, seja $ab\in E$ uma aresta qualquer. Se $a\in U$, terminamos. Caso contrário, é suficiente mostrar que existe algum caminho alternante que termina em $b$. Com $a\notin U$, ou $a$ está emparelhado ou não está. Se não estiver, $ab$ é um caminho alternante que acaba em $b$, e terminamos. Se $a$ estiver emparelhado, então existe $b'\in B$ tal que $ab'\in M$. Como $a\notin U$, existe um caminho alternante $P$ que termina em $b'$. Se $b$ está nesse caminho, tome $Pb$, e terminamos. Se não está, tome $Pb'ab$, um caminho alternante que termina em $b$, e assim terminamos.

<wrap right>$\square$</wrap>
</WRAP>