# Introduction to Graph Theory

## Objectives

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

## General characterization

12915

9.0

##### Responsible teacher

Maria do Rosário Silva Franco Fernandes

Weekly - 4

Total - 90

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.

6 –  D.B. West, Introduction to Graph Theory, Prentice Hall, 2001.

7 – M. Newman, Networks: An Introduction, Oxford University Press, 2010

### 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.

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

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

(0.5 t1) + (0.5 t2)≥ 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.

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 and shortest paths.

3. Trees and arborescence.

4. Eulerian graphs.

5. Hamiltonian graphs.

6. Matrices and Graphs.

7. Planar graphs.

8. Colouring.

9. Flows.

10. Matchings, covers, independent sets.

11. Centrality measures.

## Programs

Programs where the course is taught: