Teoria de Grafos
Código
9632
Unidade Orgânica
Faculdade de Ciências e Tecnologia
Departamento
Departamento de Matemática
Créditos
6.0
Professor responsável
Oleksiy Karlovych
Língua de ensino
Português
Objectivos
1. Dominar a linguagem matemática de Teoria de grafos e as suas aplicações à sua área de investigação.
2.Modelar problemas do mundo real usando resultados e conceitos de Teoria de Grafos.
3. Procurar soluções a problemas do mundo real usando resultados e algoritmos de Teoria de Grafos.
Conteúdo
O programa da disciplina será seleccionado de entre os seguintes tópicos:
1. Representações de grafos, subgrafos, caminhos e ciclos.
2. Conexidade: Grafos Bipartidos; Árvores e os algoritmos de Kruskal e Prim.
3. Grafos Eulerianos e Hamiltonianos.
4. Conjuntos independentes e cliques.
5. Coloração de grafos e o teorema das 4 cores (sem demonstração).
6. Grafos planares.
7. Empacotamentos e coberturas.
8. Grafos perfeitos.
9. Emparelhamentos em grafos bipartidos e não bipartidos.
10. Decomposições de grafos.
11. Teoria de grafos extrema.
12. Teoria de Ramsey.
13. Método probabilistico no estudo de teoria de grafos extrema e teoria de Ramsey.
14. Grafos aleatórios.
Bibliografia
B. Bolobas, Extremal Graph Theory, Dover, 2004.
R. Diestel, Graph Theory, 4th edition, Springer, 2010.
F. Harary, Graph Theory, Addison-Wesley, 1972.
D.B. West, Introduction to Graph Theory, 2nd Edition, Prentice Hall, 2005.