grafos:matching_alternatingpaths

Diferenças

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

Link para esta página de comparações

grafos:matching_alternatingpaths [2023/03/03 15:45] – edição externa 127.0.0.1grafos:matching_alternatingpaths [2023/03/10 12:12] (atual) – edição externa 127.0.0.1
Linha 1: Linha 1:
-==== Um pouco sobre os Emparelhamentos ====+==== Emparelhamentos ====
  
 Suponha que nos seja dado um grafo, e que seja solicitado encontrar nele tantas arestas independentes quanto possível. Como devemos fazer isso? Seremos capazes de emparelhar todos os seus vértices dessa maneira? Se não, como podemos ter certeza de que isso é realmente impossível? Surpreendentemente, esse problema básico não está apenas no cerne de inúmeras aplicações, mas também dá origem a algumas teorias de grafos bastante interessantes: **Emparelhamento**, **Empacotamento** e **Cobertura**. Suponha que nos seja dado um grafo, e que seja solicitado encontrar nele tantas arestas independentes quanto possível. Como devemos fazer isso? Seremos capazes de emparelhar todos os seus vértices dessa maneira? Se não, como podemos ter certeza de que isso é realmente impossível? Surpreendentemente, esse problema básico não está apenas no cerne de inúmeras aplicações, mas também dá origem a algumas teorias de grafos bastante interessantes: **Emparelhamento**, **Empacotamento** e **Cobertura**.
Linha 25: Linha 25:
 Caminhos alternantes desempenham um papel importante na busca prática de grandes emparelhamentos. De fato, se começarmos com qualquer emparelhamento e continuarmos aplicando caminhos ampliadores até que não seja mais possível tal melhoria, o emparelhamento obtido será sempre ótimo, um emparelhamento com o maior número possível de arestas. O problema algorítmico de encontrar tais emparelhamentos, portanto, reduz-se ao de encontrar o caminho de aumento, que é um problema algorítmico interessante e acessível. Caminhos alternantes desempenham um papel importante na busca prática de grandes emparelhamentos. De fato, se começarmos com qualquer emparelhamento e continuarmos aplicando caminhos ampliadores até que não seja mais possível tal melhoria, o emparelhamento obtido será sempre ótimo, um emparelhamento com o maior número possível de arestas. O problema algorítmico de encontrar tais emparelhamentos, portanto, reduz-se ao de encontrar o caminho de aumento, que é um problema algorítmico interessante e acessível.
  
----- 
  
 +<WRAP round tip box 100%>
 +=== Veja também: ===
 +  * [[.konigtheorem | Teorema de Emparelhamento de König]]
 +</WRAP>
 +
 +----
 <WRAP round info> <WRAP round info>
 === Referências === === Referências ===
  • grafos/matching_alternatingpaths.1677869135.txt.gz
  • Última modificação: 2023/03/03 15:45
  • por 127.0.0.1