Diferenças

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

--- grafos:konigtheorem [2023/02/21 15:46] – edição externa 127.0.0.1
+++ grafos:konigtheorem [2023/03/03 15:48] (atual) – edição externa 127.0.0.1
@@ Linha 1: / Linha 1: @@
-==== O Teorema de König ====
+==== 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 König ===
+=== 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.
@@ Linha 12: / Linha 12: @@
 //**Demonstração:**//
-Considere um grafo $G=(V,A)$ bipartido, com bipartição $\{B,C\}$. Seja $M$ um emparelhamento de $G$ de máxima cardinalidade. Para toda aresta de $M$, escolheremos uma de suas extremidades: o vértice em $C$, se existe um [[.camaltern | caminho alternante]] que termina ali, e caso contrário, escolhemos seu vértice em $B$. Chamaremos o conjunto desses vértices de $U$.
+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$.
-Perceba que qualquer conjunto de vértices que cobre $A$ deve também cobrir $M$, ou seja, a cardinalidade mínima de tal conjunto é $|M|$. Como $|U|=|M|$, basta mostrar que $U$ cobre $A$.
+{{ :grafos:part2.png?300 |}}
-Perceba, 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.
+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.