===== Emparelhamentos Estáveis =====

Após discutirmos como [[.konigtheorem | encontrar emparelhamentos com o maior número de arestas possível]] ou que [[.teoremahall | cobrem uma dada parte de um grafo bipartido]], estudaremos como encontrar emparelhamentos cujas arestas sejam as "melhores possíveis" mediante preferências definidas pelos vértices de um grafo. 

Em algumas aplicações da vida real, os [[.matching | emparelhamentos]] não são escolhidos com base em critérios globais para todo o grafo, mas envolvem o resultado de decisões independentes tomadas localmente pelos vértices participantes. Uma situação típica é que os vértices não são indiferentes a quais de suas arestas incidentes são escolhidas para combiná-los, mas preferem alguns a outros. Então, se $M$ é um emparelhamento  e $e=ab$ é uma aresta que não está em $M$, de modo que ambos $a$ e $b$ preferem $e$ à sua aresta correspondente atual (se forem emparelhados), então $a$ e $b$ podem concordar em alterar $M$ localmente incluindo $e$ e descartando suas arestas correspondentes anteriores. O emparelhamento $M$, embora talvez de tamanho máximo, seria, portanto, //**instável**//.

Nesse sentido, fixado $G = (V,E)$ um grafo, para cada $v\in V$ consideraremos $\leq_v$ uma relação de ordem total sobre o conjunto $E(v)$ de arestas que incidem em $v$. Ou seja, são satisfeitas as seguintes propriedades: 

  * **//Reflexiva://** $e \leq _v e$ para toda aresta $e\in E(v)$;
  * **//Anti-simétrica://** Se $e \leq _v f$ e $f \leq_v e$, para certas arestas $e,f \in E(v)$, então $e=f$;
  * **//Transitiva://** Dadas $e,f,g \in E(v)$ arestas tais que $e \leq_v f $ e $f \leq_v g$, tem-se que $e \leq_v g$.
  * **//Dois elementos são comparáveis://** Dadas duas arestas $e,f \in E(v)$, tem-se que $e \leq_v f$ ou $f \leq_v e$.

Nesse contexto, dizemos que $v$ //prefere estritamente// uma aresta $f\in E(v)$ a uma aresta $e\in E(v)$ se $e <_v f$, isto é, se $e\leq_v f$ mas $e \neq f$. Assim, com respeito a uma coleção de preferências $\{\leq_v : v \in V\}$, dizemos que um emparelhamento $M$ é [[.emparelhamentoestavel | estável]] se as arestas de $M$ não podem ser trocadas por outras que são melhores para suas duas extremidades, ou seja, se para toda aresta $e\in E\setminus M$ existe $f\in M$ tal que $e <_v f$ para um vértice em comum $v$ de $e$ e $f$. 

==== Teorema de Gale & Shapley: Casamento Estável ====
Através de um algoritmo relativamente eficiente, verifica-se que todo grafo [[.defbipartite | bipartido]] tem um emparelhamento estável:

<WRAP round box 100%>
=== Teorema === 
//Seja $G = (V,E)$ um grafo bipartido com partes $A$ e $B$. Fixe $\{\leq_v : v \in V\}$ uma coleção de preferências dos vértices de $G$ sobre as arestas que nele incidem. Com respeito a essa coleção, $G$ tem um emparelhamento estável.//
</WRAP>

<WRAP round box 100%>
**//Demonstração://** Fixe $M$ um emparelhamento qualquer de $G$. Com respeito a ele, diremos que um vértice $a\in A$ é //aceitável// para um vértice $b\in B$ se existe a aresta $e = ab \in E\setminus M$, que não se encontra emparelhada e é tal que $f<_b e$ para uma eventual aresta emparelhada $f\in E(b)\cap M$. Intuitivamente, para o vértice de $b$ seria mais conveniente estar adjacente a $a$ do que adjacente ao seu correspondente no emparelhamento $M$. De maneira dual, diremos que um vértice $a\in A$ está //feliz// com o emparelhamento $M$ se $E(a)\cap M = \emptyset$ ou se a aresta emparelhada $f \in E(a) \cap M$ é tal que $e=ab <_a f$ para todo $b\in B$ para o qual $a$ é aceitável. Defina então $\varphi$ uma operação sobre o emparelhamento $M$ da seguinte forma:

    * Suponha que todo $a\in A$ é ponta de algum vértice de $M$ ou não é aceitável para nenhum $b\in B$. Nesse caso, considere $\varphi(M) = M$.
    * Se o caso acima não ocorre, existe $a\in A$ que não é coberto por $M$ e é aceitável para algum $b\in M$. Nesse caso, podemos tomar $b$ de forma que $e= ab$ é o maior elemento de $E(a)$ com respeito a $\leq_a$. Assim, considere $\varphi(M) = (M\cup \{ab\})\setminus (E(b)\cap M)$.

Claramente, o vértice $a$ tomado no item acima pode não ser único, de modo que $\varphi$ não é uma função bem definida entre os emparelhamentos de $G$. Entretanto, mostraremos que, a partir do emparelhamento vazio, a aplicação sucessiva da operação $\varphi$, independentemente de seu produto, culmina em um emparelhamento estável para $G$.  

Para tanto, observamos que, se $M$ é um emparelhamento em que todos os vértices de $A$ se encontram felizes (o que é satisfeito pelo emparelhamento vazio por vacuidade), então um emparelhamento da forma $\varphi(M)$ também tem essa propriedade. Afinal, se nenhuma aresta foi removida na definição de $\varphi(M)$, isso trivialmente ocorre. Se não, $\varphi(M)$ é obtida pela remoção de uma aresta cuja ponta $b\in B$ está agora coberta por uma aresta que é estritamente melhor (com respeito a $\leq_b$), de modo que todo vértice de $A$ que ele anteriormente não aceitava continua sendo não aceito. Com isso, todo $a\in A$ continua em $\varphi(M)$ coberto pela melhor aresta entre os vértices que o aceitam ou não coberto pelo emparelhamento. Isto é, em $\varphi(M)$ todo vértice de $A$ se encontra feliz.

Mais do que isso, para todo $b\in B$ que é ponta de uma aresta $f\in M$ existe $e\in \varphi(M)\cap E(b)$ tal que $f \leq_b e$. Isto é, mediante a operação $\varphi$, as arestas que são adicionadas devem ser melhores para as suas pontas em $B$ do que as arestas anteriores. Desse modo, em no máximo $\max\{d(b) : b\in B\}$ iterações da operação $\varphi$, devemos obter um emparelhamento $M$ tal que todo vértice de $A$ se encontra emparelhado ou não é aceitável para nenhum $b\in B$. Portanto, dada uma aresta $e\in E\setminus M$ com pontas $a\in A$ e $b\in B$, verifica-se um dos seguintes casos:
  - Se $a$ não é aceitável para $b$, deve existir $f\in M\cap E(b)$ tal que $e <_b f$ por definição.
  - Se $a$ é aceitável para $b$, ele também deve estar coberto por $M$. Seja $f\in E(a)\cap M$ a aresta que o emparelha. Como o vértice $a$ se encontra feliz em $M$, tem-se que $e <_a f$. 

Logo, $M$ é um emparelhamento estável para $G$. 

<wrap right>$\square$</wrap>
</WRAP>

----
<WRAP round info 100%>
=== Referências ===
  * Reinhard Diestel. [[https://www.math.uni-hamburg.de/home/diestel/books/graph.theory/preview/Ch2.pdf |“Graph Theory”]] .5th Electronic Edition 2016, pp. 40. Acesso em 09/03/2023.
</WRAP>