Introduction to Graph Theory
Objectives
Fundamental aspects of Graph Theory, its applications and graphs algorithms.
General characterization
Code
10839
Credits
6.0
Responsible teacher
Maria Cecília Perdigão Dias da Silva
Hours
Weekly - 5
Total - Available soon
Teaching language
Português
Prerequisites
Available soon
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
Available soon
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 2018/2019 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, , (t1): all students enrolled in the course may present themselves to the 1st test.
2nd Test,, (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 2020, 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
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.