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 do Rosário Silva Franco Fernandes
Weekly hours
5
Teaching language
Português
Objectives
Fundamental aspects of Graph Theory, its applications and graphs algorithms.
Prerequisites
The student must be familiar with mathematics taught at disciplins like Linear Algebra.
Subject matter
- 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
Frequency
Frequency will be granted to any student who does not unjustifiably miss more than 2/3 of the practical classes taught. Students who have obtained it in 2016/2017 school year or who have any of the special statutes provided by law are exempt from attendance.
The evaluation is carried out through Continuous evaluation or Exam evaluation.
Continuous evaluation
During the semester two tests will be carried out with a duration of 1 hour 30 minutes and an evaluation of the practical classes (ap). Each test is rated up to a maximum of 20 values and the practical classes can be rated between 0 and 20 values.
1st Test, April 20, 2018, friday from 8:30 until 10:00, (t1): all students enrolled in the course may present themselves to the 1st test.
2nd Test, June 8, 2018, from 8:30 until 10:00, (t2): all the students enrolled in the course that have obtained a frequency or have a special status may submit to the 2nd test.
Evaluation of the practical classes: the teacher will provide at the end of the semester the classification between 0 and 20 values. This corresponds to the evaluation made by the teacher, through the student''s performance in solving the problems proposed in the classes.
The classification of continuous evaluation (CA) is obtained by the following formula:
AC = (0,45 t1 )+(0,45 t2) +(0,1 ap)
The student is approved in the course if AC is greater than or equal to 9.5 values. If AC is less than 16.5, the final grade of the course will be AC. If AC is greater than or equal to 16.5 values, the student can choose between obtaining a final grade of 16 values or performing a supplementary examination.
Exam
All the students enrolled in the course that have obtained Frequency or have special status may submit to the Exam.
At the date and time scheduled for the Exam in June 2018, any student enrolled in the course that has obtained Frequency or has special status and who has not obtained approval in the Continuous Evaluation can take the exam for 3 hours.
If the student performs the Exam (his or her classification is er) and
AE = er
is greater than or equal to 9.5, the student is approved. If AE is less than 16.5 the final grade of the course will be AE. If AE is greater than or equal to 16.5 values, the student can choose between obtaining a final grade of 16 values or performing a supplementary examination.
Grade improvement