Special Mathematics Lecture
Contact:
Serge Richard (richard@math.nagoyau.ac.jp), Rm. 247 in Sci. Bldg. A
Graph theory (Spring 2020)
Registration code : 0053621
Schedule : Wednesday (18:30  20.00)
Additional support for Japanese students:
some information

Class dates :
April 22, 29
May 6, 13, 20, 27
June 3, 10, 17, 24
July 1, 8, 15, 22

The lecture notes :
here (final version, August 2020)

The slides (265 A3 sheets) :
here (big file, app 165 MB)

Weekly summaries :
1,
2,
3,
4,
5,
6,
7,
8,
9,
10,
11,
12,
13

Study sessions :
Will be organized online on Monday or on Tuesday, from 6.30 to 8.00.
For any information, contact
Quang,
Tu Ha,
Duc Dam
Tatsunosan.

For the 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 Tsuzusan.

Works submitted by students :
Theorem on strongly connected bipartite graphs, by Chang Sun
Travelling Salesman Problem and
BellmanHeldKarp Algorithm, by Quang Nhat Nguyen
Ex. 1.4.13 of [GYA], and the powers of the adjacency matrix, by Atsuya Watanabe and Truyen Duc Dam
Proof of Proposition 2.2, by Arata Suzuki
Operations on binary search trees, by Quang Nhat Le
Proof of Theorem 1.26: a few properties of undirected and simple finite graphs, by Ha Tu Bui
About 3regular graph, and trees, by Truyen Duc Dam, Hiep Hoang Nguyen, and Atsuya Watanabe
About spanning trees, by Truyen Duc Dam and Atsuya Watanabe
The five color theorem, by Tomoya Tatsuno
Proof of Lemma 8.3, by Bui Tu Ha, Zhang Liyang, Arata Suzuki, Tomoya Tatsuno, and Eda Ruyshin
Some problems related to section 7.2 Plane graphs, by Bui Tu Ha, Kondo Ayaka, and Eda Ruyshin
About inequalities (5.1), by Quang Nhat Nguyen and Arata Suzuki
Application of graph theory in route search algorithm
for route guidance system in automobiles, by Bui Tu Ha
On regular polyhedrons, by Masahide Miyagi
Greedy algorithm, by Truyen Duc Dam and Atsuya Watanabe
Hall's marriage theorem, by Truyen Duc Dam and Atsuya Watanabe
Proof of Proposition 3.2 about trees, by Nguyen Minh Diep
Proof of Theorem 1.25 about Eulerian graphs, by Nguyen Minh Diep
On the reconstruction problem, by Nguyen Minh Diep
An Improved Inserting Algorithm to Binary Search Trees, by Zhang Liyang and Arata Suzuki
FloydWarshall algorithm, by Zhang Liyang
Network search: summary of Chapter 18 of [Ne], by Nguyen Duc Thanh

References : (electronic version available upon request)
[BG] S. Baase, A. van Gelder, Computer algorithms, Introduction to design and analysis, AddisonWesley.
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, Wold 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
Back to the main page