Os estudos de emparelhamentos em grafos surgiram no início do século XX como uma ramificação do estudo em teoria dos grafos.

Definição 1. Um grafo 𝐺 = (𝑉 , 𝐸) consiste em um conjunto de vértices 𝑉 e um conjunto de arestas 𝐸, onde cada aresta conecta dois vértices.

E um emparelhamento em um grafo é um conjunto de arestas em que nenhuma das arestas compartilha um vértice em comum. Mais formalmente:

Definição 2. Um emparelhamento 𝑀 ⊆ 𝐸 é um conjunto de arestas tal que, para quaisquer duas arestas distintas 𝑒 1 , 𝑒 2 ∈ 𝑀, temos 𝑒 1 ∩ 𝑒 2 = ∅.

Do lado teórico, Dénes Kőnig e Jenő Egerváry foram pioneiros no estudo de empa- relhamentos, provando em 1916 um de seus mais notórios resutados para uma classe específica de grafos: os grafos bipartidos. Seguindo os estudos de Kőnig, Philip Hall, em 1935, prova uma importante caracterização de emparelhamentos também para grafos bipartidos. Berge, por fim, oferece em 1957 uma caracterização para emparelhamentos maximais para todo grafo. Do lado algorítmico, Egerváry introduz em 1931 um algoritmo que resolve o problema de emparelhamento máximo ponderado em grafos bipartidos. Este leva Jack Edmonds, em 1965, a desenvolver o Algoritmo Blossom: o primeiro a resolver o problema do emparelhamento máximo em grafos gerais em tempo polinomial, marcando um avanço significativo na complexidade computacional.
Os emparelhamentos em grafos têm diversas aplicações práticas, como alocação de recursos, redes de telecomunicações, genômica, mercados econômicos, e otimização de redes de transporte. E avanços recentes incluem o estudo e apliações da extensão do conceito de emparelhamentos em estruturas mais genéricas: os hipergrafos.
Um hipergrafo 𝐻 = (𝑉 , 𝐸) consiste em um conjunto de vértices 𝑉 e um conjunto de hiperarestas 𝐸, onde cada hiperaresta pode conectar qualquer número de vértices. Um hiperemparelhamento é um conjunto de hiperarestas tal que nenhuma hiperaresta compartilha vértices com outra. Hipergrafos permitem modelar interações mais complexas, como aquelas encontradas em agrupamentos de dados de várias categorias, interações de ordem superior em redes e sistemas biológicos. O estudo de hipermatchings estende a teoria clássica de emparelha- mentos, apresentando novos desafios e oportunidades para a otimização combinatória.
Neste trabalho, dividido em três grandes capítulos, exploraremos a teoria e as aplicações dos emparelhamentos em grafos e hipergrafos. O primeiro capítulo abordará o estudo de emparelhamentos em grafos. E o segundo, em hipergrafos. No primeiro capítulo, iniciaremos estudando os resultados mais famosos, que foram anteriormente mencionados: começaremos pelo Teorema de Berge e a teoria dos caminhos aumentadores; com isso, partiremos para estudar a caracterização o Teorema de Hall; e, por fim, estudaremos o famoso teorema de Kőnig. Após este estudo teórico, estudaremos de forma aprofundada o algoritmo Blossom: utilizado para encontrar emparelhamentos máximos em grafos. Por fim, abordaremos resultados recentes em emparelhamentos em hipergrafos.