Mostrar páginaRevisões anterioresLinks reversosVoltar ao topo ==== Caminhos Alternantes ==== <WRAP round box 100%> === 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.// //Caminhos alternantes são usados para ampliar o emparelhamento.// </WRAP> <WRAP round tip box 100%> === Veja mais em: === * [[.matching&alternatingpaths | Emparelhamentos em grafos bipartidos]] </WRAP> grafos/camaltern.txt Última modificação: 2023/03/10 12:04por 127.0.0.1