2023秋 课程号：MATH5006P02
- 课程难度：中等
- 作业多少：中等
- 给分好坏：一般
- 收获大小：很多
| 选课类别：基础 | 教学类型：理论课 |
| 课程类别：研究生课程 | 开课单位：数学科学学院 |
| 课程层次：本研贯通 | 学分：4.0 |
Graph Theory (MATH5006P) --- Fall 2023
Instructor
- Tuan Tran
- Office: 1409, Management Building, East Campus
- Email: trantuan@ustc.edu.cn
Course webpage
https://ustc-comb.github.io/teaching/GT2023
Topics of the course
Basic notions; Trees; Connectivity; Eulerian and Hamiltonian cycles; Matchings; Planar graphs; Graph colourings; The matrix tree theorem; Kuratowski’s theorem; Ramsey theory; Extremal problems.
Prerequisites
Basic linear algebra, calculus.
Requirements
There will be 14 exercise sheets. You should try to solve and write up all exercises for yourself, because you will face some of them on the final exam. For each exercise sheet, submit solutions for two exercises, those you would want to be corrected. You must achieve 60% of the total score (each exercise is worth 10 points).
The new exercise sheet will normally be placed on the web shortly after the end of the Friday class. The deadline for submission is specified in the exercise sheet. It is not possible to submit the solutions after the deadline.
It would be great if you think about and discuss the exercises in small groups. You are encouraged to submit your solutions in pairs. At the beginning of each solution sheet, write the names of the team members and mark the name of the scriber (for each exercise sheet, one member of the team will write up the solutions); every student must write up at least six times (out of the fourteen).
In conclusion, you need to fulfil each of the following:
- achieving at least 60% of the point value of 2 × 14 = 24 homework problems, i.e. obtaining at least 144 points.
- writing up the solutions yourself at least six times.
Grade
The grade of the course is based on the midterm exam (30%) and final exam (70%). However, only those who fulfill the homework requirements can take the final exam.
Midterm exam: 90-minute written exam. It will tentatively take place on November 10 (Friday), 4PM to 5:30PM.
Final exam: 120-minute written exam. The date will be decided later.
Calculators and other electronic devices will not be allowed during the exams. For the final exam, you can bring one sheet of A4 paper which was written on both sides.
Literature
There will be no lecture notes. Much of the material is taken from the following books
- Reinhard Diestel, Graph Theory
- Douglas West, Introduction to Graph Theory.
- 课程难度：中等
- 作业多少：中等
- 给分好坏：一般
- 收获大小：很多
- 难度：中等
- 作业：中等
- 给分：一般
- 收获：很多
这是一门带有东南亚风情的课程。内容主要涉及到每个notation里最basic的内容和每块内容一些重要定理的proof。期中前讲了：notation（想到去考虑path和cycle的极值情况，其他没什么好说的），tree（等价定义和caylay‘s formula，给了两个proof），connectivity（vertex+edge connectively，block，menger‘s thm，比较重要的是menger‘s thm的应用），Eulerian & Hamiltonian cycle（Eulerian 的等价使用条件+ham的necessery condition，Dirac thm），Matching（二部图上的mathcing：以hall’s thm及其application为主，以及更一般图上的matching：以tutte’s thm及其application为主，特别注意和perfect matching的condition使用结合）。
整体上老师讲得有点慢（caylay‘s formula给了两种1-1 correspondence的方法，每种proof都快讲了一次课所以感觉嫌慢），不过后期感觉bar一下上来了所以现在来看这个节奏也还算合适。
作业一共13次，每次作业5题左右交2题，最多可以两人组队完成，总共至少做对16题才能参加考试。总评算分方式初定是是期中期末按比例，比较奇特，不过还算文明而且总的来说也轻松愉快。
值得一提的是作业很多题具有相当难度，就如评论区所言，这门课同样充满着“组合技巧“，但不像隔壁神秘mj组合学搞很多奇技淫巧的作业题，这里倒是布置了不少简洁有趣的小定理或二级结论（不少结论也是课堂内容一些定理/结论的直接推广）。个人认为里面有一些题目涉及到的idea是可以通过一定时间的思考慢慢get到的，而且最关键的是确实对所学知识有了更deep地理解，不少作业的证明方法就源自于上课讲的”组合技巧“。
和相关方向的同学交流了一下，个人感觉组合包括像图论这门课是一个前置知识比较少，但是所讲的内容至少从时间层面看都是比较”现代“的（所有重要定理/结论的首次证明时间主要在1900-1970间），所以slope会非常大，看上去数学复杂度不大但对很多人需要花大量时间去消化，技巧方法上做到高熟练度的难度也很大。而且这些”组合技巧“总体还是非常tricky的（IQ筛选器）。比如期中5个题属于是标答可以一面纸就能写完但都还有点tricky的题目，不过最后我大寄，可能还是bar太高了把我筛选掉了。
（先填个坑，后面慢慢补）
- 课程难度：中等
- 作业多少：中等
- 给分好坏：一般
- 收获大小：很多
- 难度：中等
- 作业：中等
- 给分：一般
- 收获：很多
怎么读老师的姓（TRAN）：https://www.youtube.com/watch?v=j4v3yk2Kjpw
期中复习越发感觉自己以前的想法过于肤浅，遂重评一下。
（貌似计科这几年只有我这么勇敢高替图论）
第一次上课，听到老师的“越南英语”（其实老师讲的还是挺标准的，是我自己英语太菜了），有点想退课。幸好和gyfer学长聊了一下，算是给了我继续选这门课的动力。
老师刚来上课的时候确实讲得有点慢，这一特点在老师讲Cayley公式第二种证明（Joyal）的时候尤为明显，因为那次课上老师一节课就讲了这一个证明😂。
之后老师逐渐找到了讲课的节奏，课堂内容逐渐充实，同时量也不会那么大。
老师上课讲的大多是每一个topic最基本的定义与定理，而大部分二级结论则留在作业中。但不要认为作业就水了，作业里也包含很多具有挑战性的题目（甚至有博资考试题，虽然我不认为这题是那次作业中最难的）。所以上课+作业还是可以cover到该cover的东西，同时也扩展了关键的方法与技巧。
作为有老本（高中搞信竟学过）的选手，上这门课最大的感受就是：图论的各个topic看似离散，实则联系紧密。第一次学习图论的时候是树状学习，学会了G=(V,E)就可以往各个方向都看一看。但其实这个“树”是有非树边的，例如网络流、连通度、匹配就联系紧密，而哈密顿回路、平面图、染色也有不少交集。而图论与别的数学分支也有很多联系，例如通过矩阵树定理引出的代数方法，平面图与染色理论与拓扑学的交集等等。
而且图论的方法与技巧是十分多样的。比如说：读完West的图论导引，学会了扩张引理，于是懂得了在处理连通度的时候可以通过加点进行规约。但是Tran Tuan老师上课采用了GTM173上的方式先证明了Menger定理的另一个版本（A-B path），而在点与边形式的Menger定理则采用删点转而考虑邻集的方式进行规约。这是一种不一样的思路（虽然我在写作业的时候还是只会傻傻的加点规约）。学习图论应该多看看各种各样的证明（一个图论定理通常有十来种证明方法，尤其是经典的那些定理），以丰富自己的图论思想。
- 课程难度：中等
- 作业多少：中等
- 给分好坏：一般
- 收获大小：很多
- 难度：中等
- 作业：中等
- 给分：一般
- 收获：很多
未选课, 旁听过一次, 更多时候是自己在跟着看讲义和作业题.
由于换了老师, 相比于往年的同名课程感觉教学内容大改革. 之前买的指定教材完全没用上, 用的是老师自己的讲义. 具体知识上我还没看完, 但感觉也大有不同.
另外还值得一提的是这门课的考核方式: 作业分不计入总评, 但只有作业得分超过50% (具体数值忘了, 大概是这个) 才能够参加期中与期末考试. 感觉这种新颖的平时分计算法还挺有好处的: 既保证学生需要按时参与到听课学习中而不能摆烂, 又避免了学生为一次作业或一题的得分而患得患失地焦虑, 可谓一举两得.
