24.8.30

申了这学期吕老师和许老师一起带的图论课的助教, 占个坑先.

25.1.3

习题1.pdf

习题课1讲义.pdf

第一次习题课选的一些题及其解答, 加上一些我个人对图论做题技巧的心得汇总.

graph_theory_note&answer.pdf

最新版的习题解答, 更新到1到6章, 暂时先放到这里. 由于要复习自己的期末24期末考之前应该是更不完接下来的部分了, 先和同学们说声抱歉.

出于相同的理由真题的解答也不会更了, 不过历年的题基本习题课1都讲了, 课群里有讲义. 没讲的课群里都回答过, 搜索聊天记录关键词为 ‘年份'.'题号'('小题号') , 例如2018.2(1).

感觉这学期的助教工作做得没有上学期带代数结构让自己满意. 寒假再详写吧.

1.7

卷子改完了, 接下来就看老师怎么给总评. 我们班同学的考试情况问我的我应该都回复了. 同学们也能看出来分数普遍比较高, 调分力度大概不会很大. 特别是和隔壁班比, 很可能两个班拿到相同卷面分的学生总评并不会一样. 考虑到今年这个班期末卷面平均分比徐老师班高了9分, 这也是没办法的事.

下面从助教角度讲一些这门课一些事务的安排:

上课: 

今年本班主要由吕老师上课, 许老师只偶尔来讲几次, 我随堂时只见过两次许老师. 今年吕老师和许老师好像还一起带一门研课 “组合数学” , 不知道讲课次数怎么分配. 隔壁班则由徐老师讲前5章, 赵老师讲后5章. Anyway, 吕老师讲课可能不够有激情, 不够生动形象好理解, 但从我随堂的次数来看至少达到了把知识点讲明白, 不漏讲不出错的标准. 并且吕老师可能是目前同学们能接触到的唯一一位能把图论讲清楚的老师了. 这样看来, 同学们开学选课时的选择还算正确.

出卷:

我没有参与出题 (不然也不可能一道课外证明题都没有) , 就我所知我们班的其它几位助教也没出, 大家都是考场上监考才看到卷子 (不然也不可能考场上又揪出一道错题) . 考虑到这次期末几乎都是摘自课本正文或习题, 大概也不需要人专门来出. 前几年好像有助教参与出卷的情况, 故言此以做今年的记录.

改卷:

今年改卷是两个班八位助教一起改两个班所有卷子, 一人改一道大题 (如果大题总数>8, 就尽量把两道简单题放在一起让一个人改) . 结合两年前我自己修图论时去查卷的情况, 22年也是如此, 应该年年都是这个模式. 改卷时并不事先出好标答, 而是每个助教先翻若干张答卷, 总结一下可能出现的各种计算结果 (如果是有多种输出的手操算法题) 或证法 (如果是证明题) , 然后就开始改, 改到不一样的做法或答案再单独判断正确性. 改完后每个助教写出自己负责的题目的标答, 汇总成整张卷子的标准答案, 随答卷上交封存. 说一下这里面会出现的, 同学们可能会关心的几个问题:

1 每个同学的作答正确与否完全由助教判断, 且助教从拿到题目自己做出一个答案到改完卷子, 并不一定会与老师或其它助教有交流, 所以就算助教自以为的解法是错的, 这个过程中也没有机会检查出来. 更可能出现的情况是助教做了一个对的答案, 但他并没有想到还可能有别的正确做法. 以今年的第5题(1)问为例说明: 选取生成树的方法有两种, 导出的不同Eular回路及对应Hamilton圈有4个, 算法输出的 “最短距离” 也有4种. 如果助教自己做了一个就开始改, 给另外三种答案都判错, 恐怕事后没有任何机会纠正这个错误, 除非这题被错判的同学全都感觉分数不对劲, 全都来查卷 (如果来查卷了倒是应该任何一位老师都有能力判断对错) . 再比如证明题, 虽然助教会检查每一种自称证出来的做法的正确性, 但不一定每个助教都有看懂每种答案的能力. 如果你的作答采用了非常规的做法 (例如无穷递降) 或者代数结构课里的概念 (例如用偏序集讨论有向图的可达性) , 某个学得马马虎虎, 考到了3.7来混助教工资的学长看不懂你在写什么, 给你打个0分, 这是完全有可能发生的事, 当助教是研究生时尤其如此. 总之同学们只要感到总评不对劲, 一定要来查卷, 并且是主动找老师问查卷的事 (具体怎么查卷见后) .

2 关于论述过程的严谨性要求与给分标准: 今年改卷时, 每题的给分点由负责该题的助教自行决定, 遇到拿不准的情况时由当时在场的老师拍板, 但总的来说决定权在赵老师和徐老师. 有几件事值得记录: ① 关于第7题的两问, 对于 “给出课表排布方案” 这一要求, 老师在决定给分标准时指定要有算法过程, 不能直接出结果. 后来我们助教指出: 求二分图的Δ-恰当边染色书上只证明了存在性, 并没有给出算法, 算法在习题7.9里, 但是这道题既没有标准解答, 更没有被出成作业, 最后老师同意直接出结果也可以给满分 (这题年年都出但是好像从未讲过算法, 感觉难评) . ② 还是第7题, 对于求最小课时数, 老师一开始要求的标准是必须先建模成二分图, 再用二分图的边色数定理直接出结果, 即使题意并未如此要求也 “既然我们学的是图论这门课那就应该默认用图论的做法” . 最后在与助教们商讨后改为: 结合课表用逻辑说明也可以给满分, 但未建模成二分图而直接使用 “边数” “边色数” 等词语仍要扣分. ③ 第5题(2)问要求证明最小生成树法求解旅行商问题近似比为2, 但这一结论依赖于距离满足三角不等式, 而题目中并未给出这一条件. 改卷时我们向老师指出这一点, 老师的回复是 “我们就默认这道题说的是现实中的距离, 满足三角不等式” , 但学生在证明近似比时如果没有提及三角不等式的条件仍要扣分, 有点呃呃……总之给分标准的决定可以说是十分随意, 即使有不合理之处制定者本人也很可能根本意识不到. 并且这一点在查卷时极难修改, 因为如果要调整标准就重判所有人的卷子, 现实上不可行.

关于给分:

我不知道总评计算方式, 只知道吕老师找我们要走了同学们的平时分和卷面分的表格 (签到的表格在老师自己那里所以不用找助教要) . 不过有几点或许可以确定: ① 总评调分的基准大概率是28开或37开计算出的分数, 因为助教改完卷后吕老师让我们在excel上列了这样计算出的同学们的分数, 大概看了一下优秀率和不及格率. ② 当某位同学卷面分高于平时分 (以100分为满分) 时, 其总评计算公式中出现的平时分替换为卷面分, 所以如果你有自信确实可以一次作业不交来考个满分拿个4.3. 至于徐班是不是这样处理我不清楚, 从我自己修代数结构和图论的情况来看并不是.

关于查卷:

徐老师专门指出: 卷面分和给分标准不能让同学们知道, 理由是卷面分一旦流出就不好调分, 不好捞人. 那么学生要决定自己来不来查卷, 就只能先看到总评. 所以顺序只可能是 批改试卷→提交总评→假期出总评→下学期开学想查卷的同学查卷. 从历年情况来看徐班的确会把优秀率捞满, 所以理由大概就真是这样. 以前我可能反对这样的做法, 但在去年有大一学生举报了数分B某班的调分公式, 导致jwc勒令每个班的老师必须严格不调按同一公式出总评之后, 我只能说, 徐老师的考量很有道理….

总而言之, 在经过了多年之后, 图论和代数结构这两门课的判卷与给分已经牢固地形成了 “宽于律己, 严以待人” 的方针: 学生不闹事 (或者没有机会发现需要闹事的因素) 是第一位的; 优秀率和挂科率不超标, 不太难看是第二位的; 至于改卷标准中的合理性, 乃至如果判卷出了错是否能够查错纠错, 虽然也重要, 但是是第三位的.

今年两个班的八位助教里, 有四位 (包括我自己在内) 是和我同一行政班的同学 (还有四位是研究生) . 改卷时是吕老师坐镇, 遇到拿不准的情况则由赵老师和徐老师最终决定. 改卷的氛围很好. 批到自己无法判断的答案, 助教们会互相之间请彼此帮忙判断对错, 但给分点还是各自按自己的标准来. 如果感觉标准过松/过严或有不合理之处, 也可以提出来大家讨论. 再加上今年题目基础, 又都是课内题, 答卷里也没有出现什么意想不到的做法, 改卷上应该没有出现差错. 但是否年年都会是这个样子, 会不会有大规模错判的情况发生, 我感觉这样一个判卷机制下真的不好说……

还有一件事值得记录: 今年有两位研究生助教是非科大本科, 自己并没有学过图论这门课, 但由于图论助教没人申请, 因为是老师的研究生被拉了过来当助教, 这学期一边自学一边做改作业, 答疑之类的工作.

为什么要写这些东西呢?

在经历了这两个学期带助教发生的事情后, 我想指出一个现象: 计科的离散数学三部曲课程, 目前从教学, 出卷再到改卷给分, 基本上处于一个烂完了的草台班子状态. (如果许老师即将不再教这门课, 吕老师, 以及教代数结构的韩文廷老师, 可能是唯二两位还在有在认真对待自己的教学, 真的想教会同学们知识的老师.) 但由于jwc的特性, 以及必修学分的硬性要求, 想把这几门课从培养方案里撤下去或是换成选修课, 短期内大概也是不现实的事, 而且也很难靠学生凭自己的努力做到. 除此之外, 这三门课的助教职位生态也已经糟糕到了极点, 形成了 教学效果不好→学生学不明白→没有人感兴趣愿意当助教→老师只能找自己研究生做助教/想偷懒拿钱的学生来当助教躺平→第二年教学效果依然不好 的恶性循环. 在此我也以个人的身份, 请求各位计算机系的同学们, 无论是已经修完了这几门课, 还是即将要修, 都能够稍微减少对离散数学课程, 乃至对数学本身的偏见. 我认为将计算机系偏理论方向用到的数学分成三门课来上, 这一科大独有的做法是有其先进性的. 这样的课程设置是否有价值, 与具体某年某一位老师来上这门课时教得好不好, 给分是不是会给同学们带来太大心理负担, 应该当做两个不同的问题分别看待. 对于相同定位的, 其它类似专业必修的, 乃至兄弟院校的计算机系广泛采用的离散数学课程, 我想任何接触过它的同学, 甚至是任何教过它的老师大概都不会否认: 它在深度上浅尝辄止, 在广度上华而不实, 其教学内容设置无法让学生理解或长久掌握其灌输的知识, 而课业带来负担与心理压力也丝毫不亚于计科离散三部曲现在最坏的现况. 同时我也衷心期望能有更多对离散数学感兴趣, 认可这三门课的价值, 而自己这三门绩点又比较好的同学, 能够申请这三门课的助教, 为改善后来的同学们的学习体验做一些贡献. 谢谢大家.

两分扣给教材，如pksq里早已经被提及过无数次的那样，这本教材仍然有些一言难尽。

本人曾经数竞学过一点点图论，当然也就从未涉及算法，说实话感觉手操算法真的有点奇葩。但就考试来看，这可是让人求之不得的送分题。

考试的话，真有点背诵课本大赛那味儿了，鄙人考前没有仔细看书，导致一道作业原题完全没写，说实话感觉有点小寄…

但这么好的助教老师真的头一回见，问的问题几乎全部秒回，整理了整本书大部分的习题，也尝尝与群友一起讨论一些很欢快的话题（班群氛围真的很好，也很活跃）

在此感谢助教哥哥的付出，这么好的助教希望以后还能遇到吧…

回忆了一下今年图论期末考试的内容：图论期末回忆.pdf（有的题目可能记漏了或者记错了），希望下一届上图论课的同学能对课程考试有个合理的预期。

这门课和代数结构相比难了很多，基本覆盖了课本前十章不带星号的内容（少部分内容包括2.4 4.4 5.6 10.3没有讲），而且基本每一章都有一些很难的定理，加上图论这门课程本身就是初等的框架下能弄出很困难的内容，所以这门课不是那种能靠考前速成的课（比如数据结构）。这门课在内容上是实实在在的数学课（虽然考试很迷……），许院长在上课的时候也基本会把握住证明的脉络，而且常常教导我们要会写证明，不要想当然地写一些似是而非的东西。（个人觉得，所谓的数理基础就应该是这种实在的课程，而不是无聊的大物实验）

课后习题和作业难度参差不齐（甚至还有错题被布置成作业，如7.9），书后面的习题提示也经常没什么用处。这里推荐一本书：《图论及其应用习题解答》张克民著，上面的解答包括了很多课本的课后习题（包括较难的5.13~5.18等题，但也有部分很难的习题不在这本书上面，如巨难的6.5）。实际上课本的习题有不少取自Bondy&Morty著的《图论及其应用》，而上面那本书正是这本书的习题解答（这本书也可以作为图论的参考资料，很经典）。

考试真的很迷，难度比作业小不少，但是有的题目出的很诡异（包括那个非平面图的题和Euler图的题），自己感觉考得也不怎么好。至于给分，大家都说没调分，但我反而感觉自己是不太配得上总评的分数的……直接出总评，不知道期末分数，所以我就给个给分超好吧。

5分是给图论本身的，2分给有教育情怀的助教，1分给老师

先占个坑，从寒假开始录制图论的视频（希望2025年暑假能如约更新全集

总而言之这门课还是一个有趣的课，但前提要是能学明白，这门课的难度其他评课也说过了，就不再赘述。

对于讲课，吕老师讲课没什么激情，像是照着念，完全没有对一个算法或者定理进行宏观感受上的描述或者强调其有趣之处。后面我有时来有时翘课，只见到一次许老师来，许老师的讲课确如评课社区所言，既有激情又有清晰逻辑，完全高了一个档次。

对于教材，我认为这本书跟很多其他课本一样，本质上是定理内容和习题答案的合集，并没有引导性，俗称“防自学设计”。可能其他课程听老师讲能听明白，于是就没有对课本产生反感，但这门课恰逢吕老师照本宣科，于是就对课本有些反感。

对于作业和考试，我高中 OI 的图论学的不错，因此没有花很多时间。

对于助教，丰助教给的习题解答和习题课讲义真的牛，框架和思路非常清晰，如果没学明白建议看丰助教的习题解答，不要死磕课本。

对于给分，说是平时期末 37 开，平时低于期末按期末算，大概率不会调分，因为期末 85+ 的人太多了。

upd: 卷面 93 但是 4.0 ，据说没调分，给分一般。

其实学的东西很有用，但王树禾教授编写的课本的确有点抽象（离散三门的课本都如此）。

xyl讲课声音比较小，对纪律要求比较严格，迟到可能会挨批，讲的快别开小差。

lm可以说是杀手了，要是代数结构和图论都在她班上那得有多惨啊，我认识的一位同学去查卷，发现助教改错了，助教当场也承认失误，结果lm强行从卷子里挑了一个刺，真的服了。

更新于2021.12.28：

今天许老板在开组会的时候吐槽图论：

• 一堆学生之前都在说考试题出的太简单，缺乏区分度，然而真要出的难的话，一个班里及格的人不超过10个；
• 只要一道题涉及一个之前没讲过的技巧，那么能做出的人就只有1/10；要是涉及两个没讲过的技巧，一个班里能有两三个做出来的就不错了；
• 出的题简单还是为了照顾你们的GPA，要是真的出难的话，又该骂我给分低了。

（之前写到另外一个班去了，改回来

许胤龙老师讲课声音比较小，没什么激情，容易犯困。吕敏老师就比较刚了，上课有一种暴力感，只要不打下课铃就会一直突突突的讲下去。

作业较难，一道题会想很长时间。

至于考试...期中、期末考试似乎只隔了两周....

考试题型大概是先让你解释概念，然后利用性质来证明。书上涉及的算法很重要，会考。

给分似乎还比较好。本来以为自己无缘优秀率，结果出分后出人意料地发现自己拿了85。（给分这么好一看就是xyl给的，lm怎么可能会调分...

课程本身比较难，但感觉老师讲的还是比较清楚的， 平时作业确实难度偏大（比如证明随意Hamilton图的三种一般形式），其实站在考试的角度要求没那么高，但站在学知识的角度来说，这门课可谓奥秘重重。

这里要吐槽课本一句，这本书不是很地道，尤其是答案部分，有时候不知所云，但也有极其精妙的解法，其水平可谓参差不齐。课本上的一些有趣的部分没有讲，但不妨一看。个别作业题难到让人吐血掀桌（搜都搜不到啊，翻书也没思路），导致写作业时耗费大量时间，然后都想烧书。个人觉得图论题的套路不一这一点决定了其困难性。

考试有点莫名其妙，算法的运用一个也没考，定理的证明一个也没考，匹配和配色部分几乎没涉及（我可是把重点压在这里了好吧），反倒是讲的不是很多的Hamilton图成了宠儿，好几个题里都涉及这种图，不是很懂为毛要考这个连充要条件都没有的毫无套路可言的类型。

老师比较严肃，但讲的条理还是比较清楚的，至于给分，不好评价，给我了一个3.7，还可以吧。离散数学比较难，名不虚传。

看到这门课这学期考完的点评才想起来这门课没有评课，对不起我有罪

先说给分，期末82，总评86，一分没调，群里有同学说37开还低了，lm给分这一块属实😅

没怎么上过课，靠平时作业对知识有个大概印象，大部分是考试前2天速通，并且个人感觉速通效果很好
图论和数理逻辑的复习我都是靠考前把课本从头读一遍，并且手写整理了书上所有定理+算法，基本上对知识点了解的就差不多了，这两门课考试都是换汤不换药，把知识理解清楚了做做往年卷看看题是怎么考的就没啥问题了，

这两门课学起来挺轻松的，而且期末把知识自己整理出来很有成就感，其实自认为自己图论学的比数理逻辑好，但是图论86数理逻辑99，个人感觉主要问题还是lm给分太不好了，听同学说隔壁同样的分给分好很多，所以建议去隔壁

喜提丰助教陪伴两学期（代数结构+图论），实在是吃的有点好，感谢丰助教，确实是CS课助教中较为少有的极为认真负责的助教。

计科图论这次考试放水放的比较多，感觉考点非常正统且几乎处处存在于课本，有点没意思，确乎好好复习就能拿高分，不好好复习各凭本事应该也不会太差。

教材虽然编排和语言比较有进步空间，但我觉得作为CS专业的图论教材已经完全达到值得使用的水平，后面题目难度参差不齐让做作业的时候稍有乐shao趣kao。

签到没去，作业泄洪式补交（期末周一下午做了七份左右喜提一堆6），最后总评=期末裸分一分没调，虽然我结果还行，不过确实是不怎么奶的样子。

计科离散三部曲之一，代数结构，图论，数理逻辑基础。

感觉代数结构的内容很多，自己记得一塌糊涂，也没有很理解透；图论这门课记的也很多，但是比代数结构轻松些，不过难度更大。但是图论的教材总归是要比代数结构要好，书上写的过程和推导基本能让人看明白。感觉图论还是比较有趣的，……吧？

上课主要是吕敏老师在上，讲的顺序逻辑和书上基本相似（有念课本之嫌），也比较清晰；许胤龙老师对课本非常熟悉，上课几乎不用看课本，不过板书字迹比较龙飞凤舞（）。

助教的工作做得非常好，强推fyfgg。丰助教算是我在科大上过的课里最负责的助教之一了（上学期代数结构徐老师班上的几位助教和某位义工助教（）也很豪），认真答疑，写教材答案，讲习题课等等，在期末周的时候更是不厌其烦地在群里解答大家的疑问。不过有个小小的建议，感觉习题课很多是作业题，隔的时间比较久，大家不太记得了，没有给一点时间让大家回顾一下，直接讲感觉不太听得进去。总体而言，fyf为什么是神！

剩下的出分再补充

许老师讲课很好，个人认为吕老师也没那么差。但是这门课的教材（王树禾《图论》第二版）非常难懂！

推荐阅读这个离散数学教程，内容不多，但读后会有豁然开朗的感觉。

此外，对书中那些繁杂的证明不要较真，近两年的考试中，证明题难度都不大。

书中涉及的算法很多，这些算法很重要，但教材对它们的介绍很confusing，建议在学习这些算法时百度一下这些算法的应用、背后的原理等，会加深对图论这个学科的认识。

说实话这门课挺难的，作业也挺多，有相当多的作业题目是相当tricky的….

至少我数学方面的注意力不是很好，每周作业都要写好几个小时

老师讲的挺快的，课下要花时间看

本学期有一次点名式小测，无期中，闭卷期末

期末的卷子是证明题+算法实操题

复习建议：认真复习教材上的所有算法，如2F算法，匈牙利算法，dijkstra…（也要会写过程）

书上的定理要学会证明（太长的几个证明可以不看，不会考）

之后有时间补一个25秋期末试题回忆版

辅修人视角来答：

感觉图论这门课，内容还是蛮有意思的，但是呢如果面向考试去学习，感觉有点割裂：一方面是各种算法，一方面是各种证明，一脚踩在了数学课和算法课的中间，感觉有点说不上来的别扭。

此外，看了往年的评论，似乎给分不太行，吓哭了。