grafos:casamentoestavel [WikiMat]

Após discutirmos como encontrar emparelhamentos com o maior número de arestas possível ou que 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 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$ é 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$.

Através de um algoritmo relativamente eficiente, verifica-se que todo grafo bipartido tem um emparelhamento estável:

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.

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$.

$\square$