9. M2-Graph Theory
Master of Physics CY University
Introduction to Graph Theory
Lecturer
C Oguey ( oguey @ u-cergy.fr ) CM 18h, TD 12h
The classic branch of graph theory has seen a revolution in the last decades
stimulated by the emergence of internet, social networks, world-wide trading
and analogous multi-scale phenomena. The goal of the course is double: 1.
provide an introduction to Graph Theory as a beautiful interdisciplinary
science in itself; 2. give a background to study the active field of complex
systems.
Syllabus
- Fundamentals
- Paths, cycles and trees
- Hamilton cycles & Euler circuits
- Planar graphs
- Electrical networks
- Vector spaces & matrices associated with graphs
- Flows, connectivity, matching
- Random graphs, generating functions
References
- B Bollobas, Modern Graph Theory, Springer 1998
- R Diestel, Graph Theory, Springer 2010, diestel-graph-theory.com
- M Newman, Networks: an Introduction, Oxford UP 2003
Grades
Based on projects (writen report + oral presentation) and/or final exam. Assessment
to be defined.
Problems
Problem set 1, set 2
Projects
Write a concise but clear report, at most 8 pages. There will also be an oral presentation.
|
|
|
| | Date due | Subject |
|
|
|
| Project 1 | tba | Individual |
|
|
|
| Oral | tba |
|
|
|
| Exam | tba |
|
|
|
| |
Subjects for studies
- Colouring [B ch 5]
- Groups: Cayley, Schreier diagrams [B ch 8]
- Adjacency matrix and Laplacian [B ch 8, N 6.13]
- Random walks [B ch 9, N 6.14]
- Knots and links [B ch 10]
- Centrality, ranking, closeness, cliques, k-plexes, k-cores [N 7.1-7.8]
- Transitivity, clustering, reciprocity, similarity, homophily, mixing [N
7.9-7.13]
- Percolation [B ch 6, N ch 16]
Other subjects are welcome. Make proposals to lecturer.
C. Oguey, Nov. 2016