Emparelhamentos em grafos e aplicações - Coelho, Ilídia Maria Amaral (2019)
O trabalho divide-se em duas partes, a primeira relativa a emparelhamentos em grafos bipartidos e a segunda relativa a emparelhamentos em grafos arbitrários. Em ambas as partes, dá-se especial destaque à caracterização de grafos que admitem emparelhamentos perfeitos e apresentam-se algoritmos para a respectiva determinação. Para além dos principais resultados que fundamentam o estudo dos emparelhamentos, descrevem-se algumas das suas aplicações, nomeadamente, na demonstração de resultados da teoria da medida, na teoria dos conjuntos parcialmente ordenados, da combinatória (coloração de arestas de grafos) da teoria das matrizes (matrizes duplamente estocásticas) e na resolução do problema de investigação operacional, conhecido por o problema do carteiro.