Special Mathematics Lecture

Contact:
Serge Richard (richard@math.nagoya-u.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

• Syllabus : the pdf file

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

• Trailers for prospective Japanese students: Deep Impact, My Chance

• 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 Tatsuno-san.

• 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 Tsuzu-san.

• Works submitted by students :
  Theorem on strongly connected bipartite graphs, by Chang Sun
  Travelling Salesman Problem and Bellman-Held-Karp 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 3-regular 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
  Floyd-Warshall 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, 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