Diferenças

Aqui você vê as diferenças entre duas revisões dessa página.

--- grafos:matching [2023/02/19 15:36] – piva
+++ grafos:matching [2023/04/10 13:20] (atual) – edição externa 127.0.0.1
@@ Linha 3: / Linha 3: @@
 <WRAP round box 100%>
 === Definição ===
-//Um conjunto $M$ de **arestas independentes** em um grafo $G=(V,A)$ é chamado de **emparelhamento**, correspondência. Os vértices de tais arestas são chamados de emparelhados.//
+//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>