2023.10.15

未选课, 旁听过一次, 更多时候是自己在跟着看讲义和作业题.

由于换了老师, 相比于往年的同名课程感觉教学内容大改革. 之前买的指定教材完全没用上, 用的是老师自己的讲义. 具体知识上我还没看完, 但感觉也大有不同.

另外还值得一提的是这门课的考核方式: 作业分不计入总评, 但只有作业得分超过50% (具体数值忘了, 大概是这个) 才能够参加期中与期末考试. 感觉这种新颖的平时分计算法还挺有好处的: 既保证学生需要按时参与到听课学习中而不能摆烂, 又避免了学生为一次作业或一题的得分而患得患失地焦虑, 可谓一举两得.

2024.11.14

一年之后终于来选了这门课, 因为老师的东南亚英语实在听不懂干脆翘了所有的课, 自己跟着写作业. (老师开学第一课讲课程事项里提到了you are not asked to attend the class, 非常有人情味. )

趁着期中尚温写个回忆卷:

1.
(a) 给定一棵标定树的Prufer code, 画出这课树.
(b) 求所有满足这样性质的树: 其Prufer code中每一位的数各不相同.
2.
(a) 证明: 连通图G中任意两条最长轨道有交点.
(b) 证明: 树T中所有最长轨道都经过同一个点.
3.
(a) 证明: 一个有2n个顶点的图恰有一个完备匹配, 则其边数不超过n^2.
(b) 对于任意正整数n, 给出一个图G满足v(G)=2n, e(G)=n^2, 且G恰有一个完备匹配.
4.
证明: 一个平面图G满足Δ(G)≤5, 且δ(G)≤4, 证明其存在4-点染色.

卷子不难或者说非常简单, 可惜考前没看平面图5色定理的证明, 光顾着背Menger, Brooks这些证明两三面的大定理了, 最后第4题半赶半口胡地写了出来. 这下真的没有必要去想它了.

这是一门带有东南亚风情的课程。内容主要涉及到每个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使用结合）。期中后讲了planar graph（考试不考），重点是coloring，以及Ramsey Theory和extreme value，解决工具穿插着probabilistic method+Matrix Tree Thm/Gessel-Viennot thm。实际上这部分内容还是很有意思而且里面的内容很丰富，但怪自己实在懒癌没怎么花时间学。。。

补充一下二阶矩方法。这也是组合中常用的概率方法，我们考察一个对象是非负整值随机变量大于0的概率大小，容易知道它不能直接被一阶矩决定，换句话说，非负整值随机变量的期望非常大无法推出其等于0的概率非常小。但如果我们同时还知道二阶矩的信息，则随机变量大于0的概率就有了下界。

参考：https://en.wikipedia.org/wiki/Second_moment_method，mit18_226f20_lec7-9.pdf。

整体上老师讲得有点慢（caylay‘s formula给了两种1-1 correspondence的方法，每种proof都快讲了一次课所以感觉嫌慢），不过后期感觉bar一下上来了所以现在来看这个节奏也还算合适。

作业一共13次，每次作业5题左右交2题，最多可以两人组队完成，总共至少做对16题才能参加考试。总评算分方式初定是是期中期末按比例，比较奇特，不过还算文明而且总的来说也轻松愉快。

值得一提的是作业很多题具有相当难度，就如评论区所言，这门课同样充满着“组合技巧“，但不像隔壁神秘mj组合学搞很多奇技淫巧的作业题，这里倒是布置了不少简洁有趣的小定理或二级结论（不少结论也是课堂内容一些定理/结论的直接推广）。个人认为里面有一些题目涉及到的idea是可以通过一定时间的思考慢慢get到的，而且最关键的是确实对所学知识有了更deep地理解，不少作业的证明方法就源自于上课讲的”组合技巧“。

和相关方向的同学交流了一下，个人感觉组合包括像图论这门课是一个前置知识比较少，但是所讲的内容至少从时间层面看都是比较”现代“的（所有重要定理/结论的首次证明时间主要在1900-1970间），所以slope会非常大，看上去数学复杂度不大但对很多人需要花大量时间去消化，技巧方法上做到高熟练度的难度也很大。而且这些”组合技巧“总体还是非常tricky的。对组合、图论的熟练度比较高的同学应该觉得期中期末都不太难，但同时要达到做到高熟练度的bar就比较困难了，因此期中期末平均分也都是60不到点。

期中略高于平均分期末高平均分10来分，感恩被老师捞了一手（总评感觉最后应该是按开根*10调分）。虽然最后成绩不咋样但不妨碍这门课程内容还是挺有意思的，而且学到的东西也比较现代（逃。

期中期末考试都不会特别简单，也不能说非常难。但是做下来整个人确实非常自闭。老师说应该会调分，希望这门课别太垃圾了/(ㄒoㄒ)/~~（毕竟在我看来这算我的主课了，主课考太垃圾会让我失去自信的😭）。

出分了，老师挺奶的。（只不过本科生没法评本研贯通课的教，就没办法看成绩这点有点愚蠢了）

课程讲义链接：Graph Theory (yufeizhao.com)

想了想还是没法给到满分。

数院的反正上的肯定是数院的图论，我主要来讲一讲这门课高替计科的课有哪些优点与不足。

首先我们来将计科图论和数院图论教的内容做一个对比。

陈峻老师的图论 = 许胤龙老师的图论 - 所有算法（这也包括所有网络流理论） - 计科图论书本后两章内容 + list coloring + Ramsey + 极值图论基础 + Kuratowski定理的证明 + Brooks定理的证明 + 格路径与LGV引理 + 图论中的概率方法 + 一点剩余的不足以单独成块的东西。

只能说数院的图论果然是数院的图论，教的东西都是比较“数学”的。首先就是和应用贴的最紧的算法一个没讲，章神的《基数选课指南》的图论部分里面也说“我们不关心应用，所以算法并不重点讲。” 《基数选课指南》里面说的图论是由侯新民老师来上的，侯老师是会讲算法的，但是“不重点”。到了陈峻老师这里，直接啥都没有了，相应的补充了纯粹数学的组合领域比较关心的东西（list coloring、Ramsey、极值图论、概率方法）。

那这时候你就要做一个取舍了，看你关心什么了。

计科的那本《图论导引》其实写的还可以（虽然是有点翻译人家东西的味道，但是架不住那本书本身就不错）。只是课后习题有点陈词滥调了点，确实问题都比较经典，但就是太经典了，有点old了。这点上是数院图论胜出了，我认为陈峻老师作业布置的还是挺有水平的。

考试的话，目前我是只考了期中考。但反正计科的考试必然比数院的简单非常多，这有好有坏，简单的容错有点低（在pksq看到过计科图论向下调分的），难的会让你很自闭，而且考智商。

总结：如果你是一个计科人，对图论、组合学比较感兴趣，你要不要拿这门课高替计科图论呢？我认为 没有很强的必要 。许胤龙老师的讲课水平确实很高，在许胤龙老师的班认真听也能学到非常多知识（徐宏力老师的教课水平我不好说）。如果你想弄个高替的噱头（就像我），来上上这门课也不错。

强推Douglas.B.West的《图论导引》（计科书大概就是参考这本的），习题丰富，内容丰富（第八章有很多进阶知识，谱图论、随机图什么的），算法也没有丢。对图论感兴趣的看看这本书一定收获颇丰。

怎么读老师的姓（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定理则采用删点转而考虑邻集的方式进行规约。这是一种不一样的思路（虽然我在写作业的时候还是只会傻傻的加点规约）。学习图论应该多看看各种各样的证明（一个图论定理通常有十来种证明方法，尤其是经典的那些定理），以丰富自己的图论思想。

Midterm Exam.pdf

期末回忆卷，我英文水平比较垃圾，大家凑合看吧。

Graph Theory Final Exam 23fall.pdf

1.老师是越南人但是我感觉翻译过来的陈峻这个名字真的很好听并且很有思想内涵。我是学物理的大二的选了这门课。当初选这门课是因为图论对计算机有用但是计科的时间段都排不开了。后来本来想把这门课退了的但是后来感觉挺有意思的就没有退。因此我这个学期的学分数量接近爆炸了。这门课对基础知识要求很少，真的只有最基本的线性代数和微积分所以大一的同学有基础的也可以来试一试，据说组合学或许可以帮助理解一些动机不知道是否是真的。

2.教材不是徐俊明老师的教材而更多是老师推荐的两本参考书，作者分别是Reinhard Diestel和Douglas West，个人认为内容和后者相似度比较高。这个学期的内容基本上就是课程简介上的，但是Kuratowski’s theorem没有讲有点可惜，如果习题课能够不占用正常的课时应该时间就够了。课上的节奏非常的慢，这从某种程度上来说是一种修养身心、感受数学的魅力的好方法，尤其对于非数学人来说。这个学期的作业我觉得是一大精髓，因为作业并不是对客商内容的简单重复的练习，而是一种自我思考自我提升的方式；并且因为作业只用交60%的次数每次是20%的题目并且不计入总评，给人的压力真的很小从而激发我们的自主性；想到其他的课程，有几门课的作业的地位是这样的呢？归根结底抑或还是教学理念的问题吧。

3.考试和作业题的难度差不多，可能还稍微低一些吧。但是毕竟有考试压力和时间压力，所以我的水平也有所下降。期中考试满分100平均分58，我因为巡回马第二问没有做出来考了90，期末考试满分110平均分56，我因为第三题直接扔了并且其他题有些过程的问题考了91。最后被调到了96分，感谢老师。

上次登录还是22年的时候，后来就没怎么玩过评课社区了。现在重新找回密码来给个好评。

总的来说，除了语言关以外，其他方面都挺好。

从备课的角度，老师有自己的一套讲义，里面的知识点从基本参考书上能找到，但是各有一点，不是那种大段的引用。相比与之前的老师的图论，比如最典的最小生成树，网络流等在这门课中均不涉及，所以是一门相对数学的图论。

老师上课讲的很细，直接导致没讲完讲义上的所有内容，但是即使这样期末也汗流浃背了。比起隔壁某照着抄一抄就一节课，还为自己一个学期讲完一个学年内容而沾沾自喜的某老师，在游戏理解上段位还是高了不是一点半点。

老师平时有在微信群里说话，会回答一部分问题，有种没有代沟的美。

老师的作业一般是5、6选两个做，出的题目也有一定的设计感，虽然不知道是不是引用书上的，不过层层递进的小问给人感觉良好。总的来说挑软柿子捏想对两个问题不大。属于有上限保下限。

老师不要求到勤，不过最后还是把讲义和考试半开卷的信息公开了，没有让旷课的人缺少信息。

老师的期中期末均分均接近60，这是有考试的书院考试中比较少见的。表现出老师并不会故意为难人，没有刻意压分等恶趣味，而且对难度把握比较精准。

从让大家学好这个角度确实是有用心的，期末考试更是贯彻平时的作业理念，完整做对一题就不会挂科，真的类目了。总而言之，是一个高上限，也高下限的课，能让所有人都得到满意的结果也挺好。当然考试坐我左边的貌似一题没做就走了，emmm，行列式也不会算吗？！？

就说这么多吧，喜欢就选，如果真喜欢肯定有较多收获，如果后面不喜欢了，正常学好作业题可保不挂。

老师讲的确实是好的，也很仔细。课程作业设置和考勤要求很人性化，作业里面往往都会有一两道比较容易的题供大家完成基本要求。

但是作为从来没有接受过专业数学领域训练的我而言，这门课本身还是非常困难，期中考试也证明了这一点，累死累活也就能得个50多分，后来助教课上重新讲期中卷子的时候才发现想到题目怎么解和严格地用数学语言表达它还是有相当的差距。

现在到了期末更是破大防，坐大牢。posa lemma 直接不知道在干什么（那次的作业我甚至一个题都没写出来…），extremal problems相对好一些，但是也是非常困难。期中之前的知识点在网上还是有比较多的参考资料可供理解的，往后的知识就有些难找了。

课程是很困难，但是确实很能扩张知识边界（至少posa lemma之前的内容我还是知道在干什么的），训练思维的严谨性，这可能就是数学的魅力吧。

有分数要求的同学一定一定慎重选择，按照我的培养方案，专业基础+数学基础的平均到75才能毕业，这门课到75对我来讲是不怎么可能了，只能从其他科目想想办法了。