===== Emparelhamento estável =====

<WRAP round box 100%>
=== Definição ===
//Dado $G = (V,E)$ um grafo, para cada $v\in V$ denote por $E(v)$ o subconjunto de arestas de $V$ das quais $v$ é uma das pontas. Fixe ainda $\leq_v$ uma ordem total sobre $E(v)$, isto é, uma relação sobre esse conjunto que satisfaz 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$.//

//Dizemos que $\leq_v$ é uma **ordem de preferência** do vértice $v$ entre seus vizinhos. Com isso, mediante uma família de ordens de preferências $\{\leq_v : v \in V\}$, dizemos que um [[.matching_alternatingpaths | emparelhamento]] $M$ é **estável** se, dada uma aresta não emparelhada $e\in E\setminus M$, existe uma aresta emparelhada $f\in M$ que possui uma extremidade $v$ em comum com $e$ tal que $e <_v f$.//
</WRAP>

----

<WRAP round tip box 100%>
=== Veja mais sobre em: ====
  * [[.casamentoestavel | Emparelhamentos estáveis]]
</WRAP>