grafos:matching [WikiMat]

Essa página está em modo somente de leitura. Você pode visualizar a fonte, mas não alterá-la. Informe-se com o administrador do Wiki, caso você ache que isso está incorreto.

==== Emparelhamento ====

<WRAP round box 100%>
=== Definição ===
//Um conjunto $M$ de **arestas independentes** em um grafo $G=(V,A)$ é chamado de **emparelhamento**. 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>

Em outras palavras, um emparelhamento de um grafo $G=(V,E)$ é um subconjunto $M \subseteq E$ tal que nenhum par de arestas de $M$ incide no mesmo vértice. Na figura abaixo, por exemplo, os conjuntos $\{2,1\}$ e $\{(0,2),(1,3)\}$ são exemplos de emparelhamentos:

{{ :grafos:emparelhament.png?250 |}}

-----
<WRAP round tip box 100%>
=== Veja mais sobre em: ===
  * [[.matching&alternatingpaths | Emparelhamentos em grafos bipartidos]];
  * [[.konigtheorem | Teorema de Emparelhamento de König]];
  * [[.teoremahall | Condição de casamento: o Teorema de Hall]];
  * [[.casamentoestavel | Emparelhamentos estáveis]];
</WRAP>