Figura: Representação de um grafo.
O que é um emparelhamento máximo?
Um emparelhamento máximo é o maior conjunto de relacionamentos (linhas) que não possuem pontos em comum num grafo. Por exemplo: se os pontos fossem computadores e se as linhas fossem os cabos de conexão e supondo que um computador somente pode se comunicar com somente um outro computador num dado instante, então o emparelhamento máximo seria o máximo de comunicação entre os computadores num dado instante. Dado o relacionamento da figura anterior, um possível emparelhamento máximo seria o relacionamento representado na figura abaixo. As linhas marcadas representam as linhas que foram escolhidas para pertencer ao emparelhamento máximo.
Figura: Representação de um grafo com emparelhado máximo. As arestas selecionadas são as pertencentes ao emparelhamento. |