**Academic Year/course: 2017/18**

##
**453 - Degree in Mathematics**

##
**27005 - Graphs and Combinatorics**

__Syllabus Information__

__Syllabus Information__

**Academic Year:**

**Subject:**

**Faculty / School:**

**Degree:**

**ECTS:**

**Year:**

**Semester:**

**Subject Type:**

**Module:**

###
**1.1. Introduction**

In the Mathematics degree of University of Zaragoza, "Graphs and Combinatorics" is a compulsory subject taught in the first year. It is included in the module Discrete Mathematics and Optimization, and is devoted essentially to the study of discrete structures. The two main topics of the subject are Combinatorics and Graph Theory. Special emphasis is placed on problem solving.

###
**4.1. Assessment tasks (description of tasks, marking system and assessment criteria)**

**Grading.**

For regular students two options:

a) - Homework (Completion of four problem sets) --- 20% of the score.

- Final exam --- 80% of the score.

b) Only final exam (100%)

For non-regular students only option b).

###
**5.1. Methodological overview**

This course covers elementary discrete mathematics. It emphasizes mathematical definitions and proofs as well as applicable methods

The course consists of lectures and solving problem classes on the topics: "permutations and combinations", "counting principles", "recurrences", "generating functions", "elementary graph theory", "shortest path problems" and "optimal flow problems".

Four problem sets will be assigned during the course. Material covered in exercises will be tested on exams.

###
**5.2. Learning tasks**

The course consists of lectures ( 2 sessions / week, 1 hour / session, 30 sessions) and solving problem classes (2 sessions / week, 1 hour / session, 30 sessions).

There are 4 problem sets. Typically, a problem set is due two week after it is assigned. By solving the problem sets a student can get 20% of the final score.

There are 4 additionals sessions devoted to solving questions related with the homework. For these additional sesssions the students are splitted into small groups.

The students can attend office hours and send questions to him/her teacher via email.

Additional information on the subject (calendar, timetable, problem sets, lecture notes,...) appears in the web page of the subject (in University of Zaragoza ADD, https://moodle2.unizar.es/add/course/view.php?id=StudentCode).

###
**5.3. Syllabus**

**Program of the subject:**

Part I

1.- Enumerative Combinatorics: Permutations and Combinations.

2.- Binomial coefficients and binomial formula.

3.- Recurrence relations. Some applications.

4.- The inclusion-exclusion principle. Applications.

Part II

5.- Generating Functions.

6.- Rational Generating Functions.

Part III

7.- Graphs: Definitions and notation.

8.- Traversing a Graph. Algorithms BFS and DFS.

9.- Applications of Graph Traversal: Connected components, strong components, bases.

10.-The number of trees and paths of a graph.

Part IV

11.- Weighted Graphs. Algorithms for the minimum spanning tree problem.

12.- The shortest path problem. Dijkstra’s algorithm.

13.- PERT-CPM algorithms for scheduling a set of project activities.

Part V

14.- Maximum flow in a network.

15.- The Ford- Fulkerson method for calculating a maximum flow.

16.- Menger’s theorems on connectivity of graphs.

17.- Maximum matching in bipartite graphs. Hall’s theorem.

18.- Some NP-Hard problems on graphs.

###
**5.5. Bibliography and recommended resources**

**Bibliography.**

*Main:*

Lecture notes of the subject at https://moodle2.unizar.es/add/course/view.php?id=8357

*Complementary books:*

Bóna, Miklós. A walk through combinatorics : an introduction to enumeration and graph theory / Miklos Bona . - 2nd ed.. Hackensack: World Scientific, 2008 |

Brualdi, Richard A. : Introductory combinatorics / Richard A. Brualdi . - 5th ed. Upper Saddle River, New Jersey : Pearson Prentice Hall, cop. 2010 |

Gross, Jonathan L.. Graph theory and its applications / Jonathan Gross, Jay Yellen . - 2nd ed. Boca Raton : Chapman & Hall/CRC, 2006 |

Lint, Jacobus Hendricus Van. A course in combinatorics / J. H. van Lint and R. M. Wilson . - [1st Ed., 2nd. repr.] Cambridge : Cambridge University Press, 1996 |

Pemmaraju, Sriram. Computational discrete mathematics : combinatorics and graph theory with mathematica / Sriram Pemmaraju, Steven Skiena . 1st publ., repr. Cambridge : Cambridge University Press, 2009 |

Stanley, Richard P.. Enumerative combinatorics / Richard P. Stanley . Cambridge ; New York : Cambridge University Press, cop. 1997-1999 |