Alguns Problemas Algorítmicos em Conjuntos Parcialmente Ordenados e o Teorema de Dilworth

Neste trabalho se determina a complexidade de problemas algorítmicos formulados sobre grafos relacionados a conjuntos parcialmente ordenados; além de um algoritmo para caracterização unívoca de conjuntos parcialmente ordenados, se determinam como de natureza polinomial ou NP-completos alguns problemas de obtenção de grafos orientados em que o número de Dilworth é minimo ou máximo. Adicionalmente são obtidos alguns resultados para problemas sobre grafos de comparabilidade e na determinação do Kernel de um dígrafo.