Go to:
Logótipo
You are in:: Start > M3026

Combinatorics and Graphs

Code: M3026     Acronym: M3026

Keywords
Classification Keyword
OFICIAL Mathematics

Instance: 2024/2025 - 2S

Active? Yes
Responsible unit: Department of Mathematics
Course/CS Responsible: Bachelor in Mathematics

Cycles of Study/Courses

Acronym No. of Students Study Plan Curricular Years Credits UCN Credits ECTS Contact hours Total Time
L:B 0 Official Study Plan 3 - 6 48 162
L:CC 0 study plan from 2021/22 2 - 6 48 162
3
L:F 0 Official Study Plan 3 - 6 48 162
L:G 0 study plan from 2017/18 2 - 6 48 162
3
L:M 0 Official Study Plan 3 - 6 48 162
L:MA 0 Official Study Plan 3 - 6 48 162
L:Q 0 study plan from 2016/17 3 - 6 48 162

Teaching Staff - Responsibilities

Teacher Responsibility
Pedro Ventura Alves da Silva

Teaching - Hours

Theoretical and practical : 3,69
Type Teacher Classes Hour
Theoretical and practical Totals 1 3,692
Pedro Ventura Alves da Silva 3,692

Teaching language

Portuguese

Objectives




To become acquainted with a variety of combinatorial concepts and techniques, with emphasis on graph theory and enumerative combinatorics.




Learning outcomes and competences

Capability of solving problems in the area. Autonomy on solving exercises.

Working method

Presencial

Program






  1. BASIC NOTIONS OF GRAPH THEORY: isomorphism, walks, subgraphs, connec- tedness, eulerian circuits, bipartite graphs.




  2. ENUMERATIVE COMBINATORICS: recurrence relations, generating functions, per- mutations, derangements, involutions, Catalan numbers, Bell numbers.




  3. PRINCIPLE OF INCLUSION-EXCLUSION: the Principle and its applications, Stir- ling numbers of the first and second kind.




  4. GRAPHS AND MATRICES: adjacency matrix, incidence matrix, minimum polyno- mial and spectrum of a graph, spectrum of a bipartite graph.




  5. TREES: forests and trees, alternative characterizations, Cayley’s Theorem, spanning trees.




  6. COLOURINGS: colouring of the vertices of a graph, chromatic polynomial and chro- matic number, critical graphs.




  7. PLANAR GRAPHS: Euler’s Formula, criteria for planarity, characterizations involving minors, Five Colour Theorem.




  8. MATCHINGS: Marriage Theorem, systems of representatives, doubly stochastic ma- trices, perfect matchings, Tutte’s Theorem.




  9. HAMILTONIAN CYCLES: Ore’s Theorem, necessary conditions for the existence of a Hamiltonian cycle.






Mandatory literature

Sebastian M. Cioabc483; A first course in graph theory and combinatorics. ISBN: 978-81-85931-98-2

Complementary Bibliography

J. A. Bondy; Graph theory. ISBN: 978-1-84628-969-9

Teaching methods and learning activities




Exposition by the teacher, discussion of exercises. List of exercises and other course materials are available on the course page at Sigarra.




Evaluation Type

Distributed evaluation with final exam

Assessment Components

designation Weight (%)
Teste 100,00
Total: 100,00

Amount of time allocated to each course unit

designation Time (hours)
Estudo autónomo 114,00
Frequência das aulas 48,00
Total: 162,00

Eligibility for exams

No requisites.

Calculation formula of final grade

The syllabus will be divided into two parts. each one evaluated by a test worth 10 points.

The second test is held simultaneously with the first season exam. In the same occasion, it is possible to repeat the first test, and the marks obrtained prevail for those students wishing it.

First season exam:

1. The final mark is the sum of the marks obtained in each test, except possibly in the following case:

2. Marks above 18 require an extra proof (oral or written).

Second season exam:

1. In the second season exam, students may repeat both tests or just one of them (except when they are just trying to improve their mark).

2.The mark of one (but only one) of the tests may be replaced a posteriori by the mark obtained in the respective test of the first season, in the version which favours most the student (except when they were approved before).

3. The final mark of the second season is the sum of the marks obtained in both tests, rounded to integers, except possibly in the following cases:

4. Students having obtained a mark equal or above 8,0 and below 9,5 have access to a complementary proof to decide if they are approved (with 10 points) or if they fail (with 8 or 9 points).

5. Marks above 18 require an extra proof (oral or written).

Special assessment (TE, DA, ...)

Examinations required under special statutes shall consist of a written test that may be preceded by an oral test, to assess if the student satisfies minimum conditions to attempt to obtain approval at the discipline in the written test.

Classification improvement

In an examen meant to improve a positive marking, it is not possible to use partial markings previously obtained.
Recommend this page Top
Copyright 1996-2024 © Faculdade de Ciências da Universidade do Porto  I Terms and Conditions  I Acessibility  I Index A-Z  I Guest Book
Page created on: 2024-07-28 at 01:24:39 | Acceptable Use Policy | Data Protection Policy | Complaint Portal