Registration code : 0053621
Schedule : Wednesday (18.30 - 20.00) in room 207 of Science Building A and on Zoom
- Syllabus : see here
- SML official rule : See here
- NU EMI : Link to the website
-
Class dates :
April 10, 17, 24
May 1, 8, 15, 22, 29
June 5, 12, 19, 26
July 3, 10, 17 (oral exam)
-
Program (tentative) :
1) The basics
2) Representations and structures
3) Trees
4) Spanning trees
5) Connectivity
6) Optimal traversals
7) Graph colorings
8) Directed graphs
9) Flows
10) Random graphs: the G(n;p) model
11) The configuration model
12) Epidemics on graphs
-
Lecture notes :
The cumulative notes
-
Study sessions :
Will be organized on an individual basis by some international students
-
Evaluation :
You need to submit the solutions of some exercises and/or the proofs of some statements. These submissions can take place at any time during the semester. If you have any question, contact me or the TA Sota Kitano.
-
Student's reports :
Inequalitities between the radius and the diameter of a finite graph, by Yat Ming Luk
On cycles of a bipartite graph, by Firdaus Rafi Rizqy
Graphic sequence and Havel-Hakimi Theorem, by Firdaus Rafi Rizqy
On Eulerian graphs, by Vic Austen
Six different characterizations of a tree, by Firdaus Rafi Rizqy and Saranakomkoop Sirawich
River crossing puzzles, by Oleh Dmytruk
Graph invariants: order and size, by Wich Moonsarn
Order of odd regular graphs, by Hevidu Samarakoon and Riichi Yatagai
The number of odd degree vertices is even, by Hevidu Samarakoon and Riichi Yatagai
Some properties of d dimensional cubes, by Muyan Ding
A lemma about unoriented trees, by Adam Matefy
Prüfer encoding and a proof of Cayley's tree formula, by Nguyen Tue Tai
Number of insertion sequences resulting in a balanced search tree, by Kanae Iwata
On powers of adjacency matrices, by Kris Sukanan
Havel-Hakimi algorithm for determining graphic sequences, by Loren Holl
Path detection with disjoint sets, by Loren Holl
Proving Catalan recurrence theorem, by Firdaus Rafi Rizqy and Saranakomkoop Sirawich
Kirchhoff's matrix-tree theorem, by Oleh Dmytruk
BEST theorem, by Yang Ming-Tian
Proof of 2-connectivity using disjoint paths, by Alberto-John Thornton and Nozomu Takeichi
On connectivity, by Ngo Gia Linh and Hirao Momona
Whitney Synthesis, by Muyan Ding
Breadth-first search trees and one application, by Ngo Gia Linh
Transformation from incidence matrix to adjacency matrix of undirected graph implemented in C, by Wich Moonsarn and Jeffrey Zhang
Eulerian properties, by Ngo Gia Linh and Hirao Momona
Insert and delete for BST, by Vilem Fiala
Ramsey Theorem, by Nguyen Tue Tai
Travelling Salesman Problem (TSP), by Alberto-John Thornton and Vilem Fiala
Equivalence of loops and bridges in dual graph, by Nozomu Takeichi
Two non-Hamiltonian graphs, by Alberto-John Thornton and Nozomu Takeichi
AVL Tree, by Vilem Fiala
The bipartite graph recognition theorem, by Chengxun Wu
Dirac's theorem, by Chengxun Wu
On finding the longest Eulerian path with multiple edges, by Byzov Martin
On the application of Bellman-Ford algorithm, by Byzov Martin
Proof of the five color theorem, by Yinan Rao
Menger's theorem, by Chengxun Wu
Proof of Berge's theorem, by Yinan Rao
Proof of Brooks' theorem, by Yinan Rao
Relationship between matrix and walks, by Narumi Ota
A greedy-based approximation algorithm for maximum matching, by Yang Ming-Tian
Calculation of strongly connected components in graphs, by Yijiang Liu
Maximum-bipartite-matching and Hall's marriage theorem, by Shino Susaki
Trading card exchanges, by Deric Yeap
Utilising adjacency matrices in biological systems: a focus on disease modelling, by Alberto-John Thornton
Kruskal's algorithm for minimum spanning tree generation, by Loren Holl and Kanae Iwata
SIR model with Leslie matrices approach and why it does not work, by Wich Moonsarn
Triangle detection in graphs, by Loren Holl and Kanae Iwata
Graceful graphs, by Oleh Dmytruk
Vertex coloring of interval graphs, by Narumi Ota
From directed graphs to strongly connected directed graphs, by Jeffrey Zhang
On properties of DFS and BFS trees, by Al Kafi Muhtasin
A comparative analysis of self-balancing binary search trees, by Yijiang Liu
Some properties of a line graph, by Hevidu Samarakoon and Riichi Yatagai
On properties of random graphs, by Al Kafi Muhtasin
Simulating the SIR model and its derivatives, by Vic Austen
Star Wars character graphs and the Kamada-Kawai algorithm, by Hevidu Samarakoon and Vilem Fiala
The Barabási-Albert model, by Adam Matefy
Exploring the traveling salesman problem, by Luke Antonov
Eulerian graph and optimal postman tour, by Shino Susaki
Whitney's connectivity inequalities, by Ruichen Li
König's theorem in graph theory, by Ruichen Li
The postman tour: definition, algorithm, and applications, by Jinuk Hong
-
References : (electronic version available upon request)
[BG] S. Baase, A. van Gelder, Computer algorithms, Introduction to design and analysis, Addison-Wesley. Useful for understanding some algorithms
[Bol] B. Bollobas, Modern graph theory, Springer. Classical textbook, more advanced
[CZ] G. Chartrand, P. Zhang, A first course in graph theory, Dover. Another possible textbook
[CH] J. Clark, D.A. Holton, A first look at graph theory, World Scientific. An easily accessible book
[Die] R. Diestel, Graph theory, Springer. A classical book
[GYA] J.L. Gross, J. Yellen, M. Anderson, Graph theory and its applications, CRC press. Our initial main reference
[KMS] I. Kiss, J. Miller, P. Simon, Mathematics of epidemics on networks, Springer, 2017. The main reference for the last lecture, seems very good
[KK] W. Kocay, D.L. Kreher, Graphs, algorithms, and optimization, 2nd edition, Chapman and Hall. With algorithms
[Ma] B. Maurer, The King Chicken Theorems. A very nice introduction to the king of chickens
[Mo] J.W. Moon, Topics on tournaments, Holt, Rinehart and Winston, Inc. Everything you want to know on tournaments
[Ne] M. Newman, Networks, second edition, Oxford University Press. One of the most recent books on networks, lot of text, but understandable
[Wal] W.D. Wallis, A beginner's guide to graph theory, Birkhauser. An introduction to the subject, NOT TOO BIG