Master of Physics CY University
Introduction to Graph Theory
C Oguey ( oguey @ cyu.fr ) CM 15h, TD 15h
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.
Chapters chosen among:
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
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
Based on projects (written report + oral presentation) and/or final exam. Assessment to be defined.
Problem set 1, set 2
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 | |
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, …[N 7.9-7.13]
Percolation [B ch 6, N ch 16]
Other subjects are welcome. Make proposals to lecturer.
C. Oguey, Oct. 2023