Guilherme Mota Pereira
    e-mail: gui.mota.pereira_2021 at usp.br

    Professor orientador: Guilherme Oliveira Mota
    e-mail: mota at ime.usp.br

    Título: Emparelhamentos em Grafos: Explorando resultados clássicos em teoria dos grafos

    Monografia
    Poster [incompleto]

    Resumo

    Dado um grafo \(G=(V,E)\), chamamos um subconjunto \(F\subseteq E\) de emparelhamento se \(e\cap f=\varnothing\), \(\forall e,f\in F\) distintos. Neste trabalho, estudaremos os principais teoremas clássicos sobre emparelhamentos em grafos. Começaremos com uma breve introdução à teoria dos grafos. Seguimos para o Teorema de Berge na caracterização de emparelhamentos máximos em grafos gerais. Em seguida, apresentamos resultados em grafos bipartidos como o Teorema de König sobre emparelhamentos máximos e cobertura de vértices mínima, o Teorema do Casamento de Hall e o Teorema da Deficiência de Hall. Finalizamos voltando a grafos gerais, provando o Teorema de Tutte na caracterização de emparelhamentos perfeitos e a Fórmula de Tutte-Berge.