Diferenças
Aqui você vê as diferenças entre duas revisões dessa página.
| Ambos lados da revisão anterior Revisão anterior Próxima revisão | Revisão anterior | ||
| grafos:camaltern [2023/02/19 15:34] – edição externa 127.0.0.1 | grafos:camaltern [2023/03/10 12:04] (atual) – edição externa 127.0.0.1 | ||
|---|---|---|---|
| Linha 3: | Linha 3: | ||
| <WRAP round box 100%> | <WRAP round box 100%> | ||
| === Definição === | === Definição === | ||
| - | Considere um grafo [[defbipartite | bipartido]] $G=(V,A)$ com bipartição $\{B,C\}$. Seja $M$ um emparelhamento para esse grafo. Dizemos que um caminho que começa em $a\in B$ não emparelhado e contém arestas de $A$ e de $A\backslash M$ de forma alternada é um caminho alternante em relação a $M$. Um caminho alternante que termina em um vértice não emparelhado é chamado de caminho ampliador, pois pode ser usado para construir um emparelhamento maior. | + | //Considere um grafo [[defbipartite | bipartido]] $G=(V,A)$ com bipartição $\{B,C\}$. Seja $M$ um emparelhamento para esse grafo. Dizemos que um caminho que começa em $a\in B$ não emparelhado e contém arestas de $A$ e de $A\backslash M$ de forma alternada é um caminho alternante em relação a $M$. Um caminho alternante que termina em um vértice não emparelhado é chamado de caminho ampliador, pois pode ser usado para construir um emparelhamento maior.// |
| - | Caminho alternante usado para ampliar o emparelhamento. | + | //Caminhos alternantes são usados |
| + | </ | ||
| + | <WRAP round tip box 100%> | ||
| + | === Veja mais em: === | ||
| + | * [[.matching& | ||
| </ | </ | ||