| |
| grafos:matching_alternatingpaths [2023/02/21 15:17] – edição externa 127.0.0.1 | grafos:matching_alternatingpaths [2023/03/10 12:12] (atual) – edição externa 127.0.0.1 |
|---|
| ==== Emparelhamentos, Empacotamento e Cobertura ==== | ==== 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**. |
| |
| |
| ==== Emaparelhamento em grafos bipartidos ==== | ==== Emparelhamento em grafos bipartidos ==== |
| |
| Para esta seção, fixemos $G=(V,A)$ como sendo um grafo bipartido com as partições $\{B,C\}$.E denotemos os vértices da partição $B$ como $b,b', \dots$, bem como os vértices de $C$ como $c,c',\dots$. E comecemos a seção com a definição de **Emparelhamento**. | Para esta seção, fixemos $G=(V,E)$ como sendo um grafo bipartido com as partições $\{A,B\}$.E denotemos os vértices da partição $A$ como $a,a', \dots$, bem como os vértices de $B$ como $b,b',\dots$. E comecemos a seção com a definição de **Emparelhamento**. |
| |
| |
| <WRAP round box 100%> | <WRAP round box 100%> |
| === Definição: Emparelhamento === | === Definição: Emparelhamento === |
| //Um conjunto $M$ de **arestas independentes** em um grafo $G$ é chamado de **emparelhamento**, correspondência. Os vértices de tais arestas são chamados de emparelhados. $M$ é um emparelhamento de $U \subseteq V$ se todo vértice em $U$ é incidente com uma aresta em $M$. Os vértices em $U$ são então chamados de emparelhados (por $M$); vértices não incidentes com uma aresta de $M$ são desemparelhados. | //Um conjunto $M$ de **arestas independentes** em um grafo $G$ é chamado de **emparelhamento**, correspondência. Os vértices de tais arestas são chamados de emparelhados. $M$ é um emparelhamento de $U \subseteq V$ se todo vértice em $U$ é incidente com uma aresta em $M$. Os vértices em $U$ são então chamados de emparelhados (por $M$); vértices não incidentes com uma aresta de $M$ são desemparelhados.// |
| // | |
| </WRAP> | </WRAP> |
| |
| \\ | \\ |
| À luz desta definição, nos perguntamos: como podemos encontrar um emparelhamento em $G$ com o maior número possível de arestas? Vamos começar considerando um emparelhamento arbitrário $M$ em $G$. Um caminho em $G$ que começa em $B$ em um vértice não emparelhado e então contém, alternadamente, arestas de $A \setminus M$ e de $M$ , é um [[.camaltern | caminho alternante]] em relação a $M$. Observe que o caminho pode ser trivial, ou seja, para consistir apenas em seu vértice inicial. | À luz desta definição, nos perguntamos: como podemos encontrar um emparelhamento em $G$ com o maior número possível de arestas? Vamos começar considerando um emparelhamento arbitrário $M$ em $G$. Um caminho em $G$ que começa em $A$ em um vértice não emparelhado e então contém, alternadamente, arestas de $E \setminus M$ e de $M$ , é um [[.camaltern | caminho alternante]] em relação a $M$. Observe que o caminho pode ser trivial, ou seja, para consistir apenas em seu vértice inicial. |
| |
| Um caminho alternante $P$ que termina em um vértice desemparelhado de $C$ é chamado de **caminho aumentado**, porque podemos usá-lo para transformar $M$ em um emparelhamento maior: a diferença simétrica de $M$ com $E(P)$ é novamente um emparelhamento (considere as arestas em um determinado vértice), e o conjunto de vértices emparelhados é aumentado em dois, as extremidades de $P$. Observe na figura a seguir, o aumento do emparelhamento $M$ pelo caminho alternante $P$: | Um caminho alternante $P$ que termina em um vértice desemparelhado de $B$ é chamado de **caminho ampliador**, porque podemos usá-lo para transformar $M$ em um emparelhamento maior: a diferença simétrica de $M$ com $E(P)$ é novamente um emparelhamento (considere as arestas em um determinado vértice), e o conjunto de vértices emparelhados é aumentado em dois, as extremidades de $P$. Observe na figura a seguir, o aumento do emparelhamento $M$ pelo caminho alternante $P$: |
| |
| {{ :grafos:camaltern.png?400 |}} | {{ :grafos:part.png?450 |}} |
| |
| 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 de aumento 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 === |