Introduction to Graph Theory
Code
10839
Academic unit
Faculdade de Ciências e Tecnologia
Department
Departamento de Matemática
Credits
6.0
Teacher in charge
Maria Cecília Perdigão Dias da Silva
Weekly hours
5
Total hours
70
Teaching language
Português
Objectives
Fundamental aspects of Graph Theory and its applications (graphs algorithms).
Prerequisites
The student must be familiar with mathematics taught at disciplins like Linear Algebra I and II.
Subject matter
1. Basics.
2. Connectivity.
3. Trees and arborescence: Algorithms of Kruskal and Prim.
4. Eulerian graphs: Fleury''''''''s Algorithm.
5. Hamiltonian graphs.
6. Matrices and Graphs.
7. Planarity: Euler''''''''s Formula. Kuratowski''''''''s Theorem.
8. Colouring: Chromatic Number. Chromatic polynomial.
9. Fulkenson-Ford''''''''s Algorithm.
10. Hall''''''''s Theorem.
Bibliography
1 – I. Cabral., Grafos e Aplicações, Texto Teórico e Exercícios, Departamento de Matemática, Universidade Nova de Lisboa, 1997,1998.
2 – C. Berge, Graphs, Second revised edition, North-Holland, London, 1985.
3 – R.J. Wilson, J.J. Watkins, Graphs: An Introductory Approach, John Wiley &Sons, New York, 1990
4 – J. Gross, J. Yellen, Handbook of Graph Theory, CRC Press, 2004.
5 – N. Hartsfield, G. Ringel, Pearls in Graph Theory: A Comprehensive Introduction, revised and augmented, Academic Press, Boston, 1994.
Teaching method
Classes consist of oral explanation of the theory and of solving problems.
Evaluation method
There are three tests that can substitute the final exam in case of approval. Otherwise the student must succeed the final exam. More detailed rules are available in the Portuguese version.