Diferenças
Aqui você vê as diferenças entre duas revisões dessa página.
| Ambos lados da revisão anterior Revisão anterior Próxima revisão | Revisão anterior | ||
| grafos:matching [2023/03/10 12:03] – piva | grafos:matching [2023/04/10 13:20] (atual) – edição externa 127.0.0.1 | ||
|---|---|---|---|
| Linha 3: | Linha 3: | ||
| <WRAP round box 100%> | <WRAP round box 100%> | ||
| === Definição === | === 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. $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.// | + | //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.// |
| </ | </ | ||
| + | |||
| + | 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, | ||
| + | |||
| + | {{ : | ||
| ----- | ----- | ||