grafos:konigtheorem

Diferenças

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

Link para esta página de comparações

Ambos lados da revisão anterior Revisão anterior
Próxima revisão		 Revisão anterior
grafos:konigtheorem [2023/02/23 10:54] – pivagrafos: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. 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%>  <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  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. cobre as arestas.
Linha 13: Linha 13:
  
 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$. 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. 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.
  • grafos/konigtheorem.1677160448.txt.gz
  • Última modificação: 2023/02/23 10:54
  • por piva