Introdução à Teoria de Matróides
Código
10831
Unidade Orgânica
Faculdade de Ciências e Tecnologia
Departamento
Departamento de Matemática
Créditos
6.0
Professor responsável
Júlia Maria Nunes Loureiro Vaz de Carvalho, Maria do Rosário Silva Franco Fernandes
Total de horas
56
Língua de ensino
Português
Objectivos
Pretende-se dar a conhecer uma teoria que uniformiza conceitos apreendidos noutras disciplinas (matrizes; grafos; conjuntos parcialmente ordenados).
Conteúdo
1. Conceitos Fundamentais
a. Definição de matróide e exemplos.
b. Base de um matróide.
c. Função característica.
d. Circuitos.
2. Conjuntos parcialmente ordenados e matróides
a. Breve revisão de conjuntos parcialmente ordenados.
b. Matróides e diagramas de Hasse.
3. Matróide dual
a. Definição e exemplos.
b. Alguns resultados sobre o matróide dual.
4. Matróides obtidos a partir de outros matróides
a. Restrição de um matróide.
b. Contração de um matróide.
c. União de matróides.
5. Conexidade
a. Definição de matróide conexo.
b. Algumas caracterizações de matróide conexo.
6. Grafos e Matróides
a. Grafos homeomorfos e submatróides.
b. Grafos planares e matróides duais.
7. Matróides transversais
a. Transversais e transversais parciais; Teorema de Rado-Hall.
b. Matróide transversal.
c. Aplicações do Teorema de Rado-Hall.
8. União de Matróides
a. k-base de um matróide.
b. Número de cobertura de um matróide.
c. Número de cobertura de um elemento de um matróide.
Bibliografia
1. D. J. Welsh. Academic Press, London, 1976.
2. J.G. Oxley, Matroid Theory, Oxford University Press, Oxford, 1992.