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/04/10 13:07] – piva | grafos:matching [2023/04/10 13:20] (atual) – edição externa 127.0.0.1 | ||
|---|---|---|---|
| Linha 4: | Linha 4: | ||
| === Definição === | === 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.// | //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, | ||
| + | |||
| + | {{ : | ||
| ----- | ----- | ||