grafos:empperfeito [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 Maximal e Emparelhamento Perfeito(Máximo) ====

<WRAP round box 100%>
=== Definição: Emparelhamento Maximal ===
//Um emparelhamento é chamado de emparelhamento maximal se
nenhuma aresta do grafo puder ser adicionada sem que a
propriedade de não-adjacência entre as arestas seja destruida.//
</WRAP>

----

<WRAP round tip box 100%>
=== Observação ===
//Observe que um grafo pode ter vários emparelhamentos maximais.
Em geral, estamos interessados no emparelhamento maximal com o
maior número possível de arestas, chamado **emparelhamento
máximo.**//
</WRAP>

----

<WRAP round box 100%>
=== Definição: Emparelhamento Perfeito  ===
//Um emparelhamento máximo é chamado de **emparelhamento perfeito** se todo vértice do grafo é extremidade de alguma aresta do emparelhamento.//
</WRAP>

Na figura abaixo,em $G_1$ temos um  emparelhamento maximal, mas não máximo;em $G_2$ temos um emparelhamento máximo, mas não perfeito; em $G_3$ temos um emparelhamento perfeito.

{{ :grafos:grafoperf.png?400 |}}