Program of

Mathematical Methods (part A)

(Prof. M. Ferri)

See the very nice class of academic year 2015-2016.

(Here the classes of 20013-2014, 2009-2010 and of 2008-2009, always in my heart.)

The course consists of two parts. Part A is dedicated to Graph Theory. Part B is held by Prof. Simonetta Abenda Ph.D.
The following program will be updated during the course.


Theory

1. Graphs and subgraphs (1.1 to 1.7; 1.8 up to first 24 lines of page 19).
Theorems: Thm. 1.1 (with proof), Cor. 1.1 (with proof), Thm.1.2 (with proof)
Exercises: 1.1.3, 1.2.1, 1.2.3, 1.2.4, 1.2.10, 1.2.12(c), 1.3.1, 1.4.4, 1.5.1, 1.5.4, 1.5.5, 1.5.6(a), 1.6.1, 1.6.2, 1.6.3, 1.6.11, 1.7.2, 1.8.4.
2. Trees (2.1; 2.2 up to Cor. 2.4.2; 2.3 up to Thm. 2.7; 2.4; 2.5 up to Thm. 2.10 excluded).
Theorems: Thm. 2.1 (with proof), Thm.2.2 (with proof), Cor. 2.2, Thm. 2.3, Thm. 2.4, Cor. 2.4.1, Cor. 2.4.2 (with proof), Thm. 2.7, Thm. 2.8 (with proof), Thm. 2.9.
Exercises: 2.1.4, 2.4.3.
3. Connectivity (3.1; 3.2 up to Cor. 3.2.2).
Theorems: Thm. 3.1, Thm. 3.2, Cor. 3.2.1, Cor. 3.2.2
4. Euler tours and Hamilton cycles (4.1; 4.2 up to Cor. 4.4; 4.3 up to Thm. 4.7; 4.4: first 10 lines).
Theorems: Thm. 4.1, Cor. 4.1, Thm. 4.2, Thm. 4.3 (with proof), Thm. 4.4, Cor. 4.4, Thm. 4.7.
Exercises: 4.1.1, 4.1.2.
5. Matchings (5.1, 5.2; 5.4: first 8 lines).
Theorems: Thm. 5.1, Thm. 5.2, Cor. 5.2, Lemma 5.3, Thm. 5.3.
Exercises: 5.1.1(a), 5.1.2, 5.1.5(b).
6. Edge colourings (6.1: first 20 lines, Thm. 6.1; 6.2: Thm. 6.2; 6.3: first 21 lines).
Theorems: Thm. 6.1, Thm. 6.2.
7. Independent sets and cliques (7.1; 7.2 up to the table of numbers).
Theorems: Thm. 7.1 (with proof), Cor. 7.1 (with proof), Thm. 7.2, Thm. 7.3, Thm. 7.4.
8. Vertex colourings (8.1 up to Cor. 8.1.2; 8.2; 8.3: only Thm. 8.5; 8.4; 8.5 up to Thm. 8.7; 8.6).
Theorems: Thm. 8.1 (with proof), Cor. 8.1.1 (with proof), Cor. 8.1.2 (with proof), Thm. 8.4, Thm. 8.5, Thm. 8.6 (with proof), Cor. 8.6, Thm. 8.7.
Exercises: 8.4.1, 8.4.2, 8.6.2.
9. Planar graphs (9.1 excluding Thm. 9.1; 9.2; 9.3; 9.5 without lemmas and without proof; 9.6 up to Thm. 9.12 excluded, without proof; mind the footnotes!).
Theorems: Thm. 9.2 (with proof), Thm. 9.3 (with proof), Thm. 9.4 (with proof), Thm. 9.5 (with proof), Cor. 9.5.1 (with proof), Cor. 9.5.2 (with proof), Cor. 9.5.3 (with proof), Cor. 9.5.4 (with proof), Cor. 9.5.5 (with proof), Thm. 9.10, Thm. 9.11, footnote at p. 157.
Exercises: 9.1.2.
10. Directed graphs (10.1; 10.2 up to Cor. 10.1; 10.6 up to Thm. 10.5).
Theorems: Thm. 10.1 (with proof), Cor. 10.1 (with proof), Thm. 10.5 (with proof).
Exercises: 10.1.1

Exercises

Modelling problems with graphs. Writing matrices associated with graphs. Computing graph invariants. Solving elementary graph problems: Shortest path problem (by Dijkstra's Algorithm), Connector problem (by Kruskal's algorithm), Chinese postman problem (by Fleury's algorithm), finding minimal coverings and maximal independent sets (by logical operations), making a 2-edge-connected graph diconnected. Building a maximal flow in a network.
The student is bound to (try to) solve the book exercises listed above for each chapter.

Textbooks

Official textbook:

J.A. Bondy and U.S.R. Murty, "Graph theory with applications",
North Holland, 1976.
Freely downloadable at http://book.huihoo.com/pdf/graph-theory-With-applications/ (24 MB).

Support textbooks:

J.A. Bondy and U.S.R. Murty, "Graph theory",
Springer Series: Graduate Texts in Mathematics, Vol. 244 (2008)

R. Diestel, "Graph theory", Springer Series: Graduate Texts in Mathematics, Vol. 173 (2005)
Freely downloadable at http://diestel-graph-theory.com/basic.html (3 MB).


Exams

A mid-term test will be given in December, at a date which will be communicated in class and here. The mid-term test MUST be passed with a score of at least 14 (over 24). If you don't pass, you must recover it; the dates for recovering coincide with the dates of the written exams of the freshmen (see Prossimi appelli - Geometria e Algebra t (prova scritta). For doing so you have to communicate to me WHEN you want to take it before the final exam.

Apply for the final exam at AlmaEsami. The final exam is as follows: I propose two subjects; you choose one and write down all what you remember about it, and then we discuss on your essay and in general about the chosen subject.


Supplementary material:

Example 1 of mid-term test and its solution.
Example 2 of mid-term test and its solution.

Projected slides: Smallworld (0.2 MB), Configuration spaces (7.8 MB).

Have a look at the demos of graph theory.