Emparelhamento

Conceitos básicos de emparelhamento em grafo

O que é um grafo?

Grafo é uma maneira de se representar relacionamentos entre objetos. Em computação, é utilizar pontos para representar objetos e linhas entre os pontos que possuem um relacionamento entre si. Os pontos poderiam ser computadores e as linhas poderiam ser os computadores que possuem um cabo de conexão entre si. Um outro exemplo, seria os pontos representando pessoas e as linhas representando um laço de amizade entre elas. Um exemplo de um relacionamento está representado na figura abaixo:

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.