Introduction to Graph Theory

Objectives

Fundamental aspects of  Graph Theory,   its applications  and graphs algorithms.

General characterization

10839

6.0

Responsible teacher

Maria Cecília Perdigão Dias da Silva

Weekly - 5

Total - 70

Português

Prerequisites

The student must be familiar with mathematics taught at disciplins like Linear Algebra.

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

Remote evaluation

We inform that, when performing any of the ITG distance exams, each student commits himself under honor to

1. Always be connected via Zoom only to Teachers, keeping the microphone and video of your equipment always on during the test.
2. Do not contact ANYONE during the tests by any means, with the possible exception of contact with the Teachers (only via Zoom Chat) for any pertinent clarification on the statement.
3. Perform the tests WITHOUT any consultation of available elements, whether on paper, audio, video or electronic media.

Continuous evaluation

Throughout the semester, there will be two tests lasting 1 hour 30 minutes and an evaluation of the classes. Each test has a classification up to a maximum of 20 values ​​and the evaluation of practical classes will be between 0 and 20 values.

All students who are enrolled in the Course of Introduction to Graph Theory can take any test at any time.

Class evaluation: at the end of the semester, the teacher will provide a classification between 0 and 20 points. This corresponds to the evaluation made by the teacher, through the student''''s performance in solving the problems proposed in Moodle or in Homework.

Let t1 and t2 and aa be the classifications obtained in the 1st test, 2nd test and in the Assessment of classes, respectively. A student can only pass the subject by continuous assessment if

(0.45 t1) + (0.45 t2) + (0.1 aa) ≥ 9.5

In this case the final classification will be given by this average rounded to the units, except if this average is greater than or equal to 16,5, in which case the student may choose to stay with the final classification of 16 or take a complementary test to defend note.

Appeal Exam

All students enrolled in the course can take the Appeal Exam.

On the date and time foreseen for the Examination of the Appeal, any student enrolled in the discipline and who has not passed the Continuous Assessment can take the Appeal exam which will last 2h 30m. If the student takes the Appeal Exam, his / her classification is the one obtained in this exam.

If the classification is greater than or equal to 9,5 and less than or equal to 16,4, the student is approved with this classification, rounded to the nearest integer. If the classification is greater than or equal to 16,5, the student may choose to stay with the final classification of 16 or take a complementary test to defend his grade.

Grade improvement

Any student wishing to present a grade improvement must register for this purpose at CLIP (information at the Academic Office). The classification of the improvement exam is obtained according to what is indicated for the exam. If this result is higher than that already obtained in the discipline, it will be taken as a final grade. Otherwise, there is no grade improvement.

Final considerations

The General Regulations of the FCT-UNL apply in everything the present Regulation does not mention.

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.

Programs

Programs where the course is taught: