推荐和代数结构的评课搭配食用: https://www.icourse.club/course/14363/

·

内容简介

在读者没有了解关于图的一些定义的前提下, 几乎不可能根据课本的章节名字有意义地介绍每个部分讲什么. 因此建议读者至少粗看一遍课本的第一章, 然后再看目录中每一章的标题. 这里只讲一点抽象的结构:

图论的知识和代数结构有相似也有不同. 相似之处在于二者都有抽象的特点, 学习的过程中很需要学习者 "凭空想象" 的能力--即使图论有时可以寻求可视化的理解, 也要注意画出来的 "图" 与图论中的图是不同的, 并且没有很强的关联性. 有时拿画的图来理解图论反而会有误导效果, 比如你可能默认了一些看上去很显然, 但证明并不平凡甚至错误的结论.

不同之处主要在于图论的知识体系比较零散. 如果说代数结构每一章的知识结构是链式的 (不学群就没有办法学环和域) , 那么图论的知识结构就是树状的: 学了第1章图的基本概念, 几乎就可以开始接触2~10章中的任何地方; 即使第3章连通性学得云里雾里, 也不妨碍你看第4章可平面图 (这么说其实不太精确, 比如学可平面图的染色显然需要先学了可平面图) . 对学习者来说, 这种松散型一方面作了个保底: 不用担心一个地方没学好影响大局; 另一方面也使得要记的东西更多, 所谓 "融会贯通" 的作用更小.

(11, 12章是偏科普性的内容. 我们这届考试不做要求, 徐老师也意料之中地不讲. )

此外, 图论有很多学习内容是理解解决某个特定问题的算法, 考试也有相当一部分题是让你对一个具体图跑一个算法. 这使得至少决定要应付这门课的同学在这方面可以放心大胆地 "不理解证明, 只知道成立" .

·

讲课

徐老师的讲课风格在代数结构中的点评已有介绍. 这学期据我的舍友说情况更上一层: 不但绝对不跳出课本一句话, 甚至连课本上的内容也不能复述完全. 讲课速度很慢 (发生过一星期没讲完一个知识点因而没有布置作业的情况) , 有时看时间不够或者自己搞不明白就说 "这里我们不细讲" --不过这个事情是我间接听说的, 仅供参考, 真实性自行取舍.

·

作业&考勤

和代数结构也基本一样, 甚至作业量更少了.

考勤方面, 有一天因为到的人太少而愤怒第地点名 (我的一位舍友只迟到了30s好像都没记到课) . 建议的应对方式上一篇也讲了, 此不赘.

(结课后补充: 这次点名好像对总评没有影响)

·

考试

2022秋期末 (开学) 考回忆版:

1. 给定一个图:
(1) 回答是否是二分图并给出理由;
(2) 回答是否是可平面图, 若是则给出面数, 否则说明理由;
(3) 回答是否是Hamilton图并给出理由;
(4) 对一对点执行Dijkstra算法求最短路径.
2. 给定一个二分图及其一个匹配, 用匈牙利算法将其优化为最大匹配.
3. 给定一个情境 (教师用教室上课) 并问一些特定的最优问题, 利用图论的染色知识可求解.
4. 证明: 如果一个图G有Hamilton路径, 则任取V(G)一个非空真子集S, ω(G-S)≤|S|+1.
5. 证明: 一棵树T的所有点度数均为奇数, 当且仅当任取T的一条边e, T-e得到的两个连通片均为奇子树.
6. 证明: 对于一个k色临界图, 其任一割集S不是团, 即S的生成子图G(S)不是完全图.
7. 在考虑同构与不考虑同构的情况下, 分别求出将K5定向成竞赛图的方法数. 对于考虑同构的情况, 写出所有竞赛图.
(有传言说助教会按 “写出所有度数序列” 批改. ~~如果是真的, 鉴定为自己都没学懂.~~ )
8. 利用最大流最小截定理证明König-Egerváry定理.
(不知道直接证明给不给分. )
9. 给定一个基本关联矩阵 (ν=4, ε=5) , 在不画出图的前提下判断:
(1) 其是否是连通图;
(2) 其是否是Eular图;
(3) 其是否是可平面图.

·

学习

课本据同班同学说有一些错误, 但没有代数结构那么高频. 启发性方面比代数结构那肯定是好了不少, 但也仅限于到了及格线.

我对图论没有对抽代那么感兴趣, 也没有自己去找教材完善知识体系, 只是把书上给出的定理都证过了一遍 (除了最难的第3章) . 针对图论的抽象性, 上篇提到的学习建议依然成立.

需要提的一点不同的是: 代数结构的证明格外需要的是思路, 而图论的证明格外需求的除此之外还包括严谨性. 如果不死扣定义出发写证明, 很多定理可能看似平凡得像废话, 但实则你的证明过程是有漏洞的.

推荐的参考书方面, 助教推荐的是清华的教材和习题解答.

·

总评

(23.6.7最终更新)

据ics的群友说, 今年由于许徐两个班的期末考试平均分差距过大 (许班>>徐班) , 赵功名老师决定将两个班合并起来给分, 优秀率也合起来算. 换言之, 许班的优秀率会超40%而徐班则会偏低. 从最后出来的总评结果来看, 合并算分的情况的确是存在的, 但两个班的优秀率依然是各自给的, 这也就使得徐班3.7非常好拿, 从周围同学的情况来看只要作业按时交, 考试把基础分拿到, 基本就比较有可能拿优秀了.

作者期末是班上最高分, 查卷的时候偷瞄了一眼助教的电脑, 看到自己卷面90, 平时分好像是62.5 (因为一半作业是迟交的) . 总评则是89/3.7, 按照老师明面上给出的 "严格三七开" 来算怎么都到不了这个数, 可见老师还是捞了的. 在此也提醒读者千万要按时写作业, 哪怕不会至少也把自己能想到的东西写上去按时交了 (何况你看我都编了份习题解答了) . 不要像我一样平时弃分如土, 总评出了的时候又来懊悔. 除非你对这门课的掌握到了驾轻就熟的地步, 不然关键时候作业分对总评的影响还是相当可观的.

总得来说这门课给分挺好. 但又据流传的内部消息称, 徐老师以后不会带图论班了. 这份评课总结出的修课方法将来不一定还适用, 也请读者仅作参考.

·

其它补充

①

隔壁班的许胤龙老师据说讲课水平很高. 我去听过第一节: 至少讲课风格上与照本宣科大不相同, 而是 在自己认为有必要的地方着重解析地讲, 平凡的地方则少花时间; 实际效果方面, 由于第一节的内容没什么难度, 不具有参考性, 据隔壁班同学说和徐宏力老师是天壤之别. 但许班的作业量远超徐 (好像会把所有大部分课后题都布置下去) , 想学真东西的同学可以考虑采用 "选一门赚绩点, 旁听另一门学知识" 的模式.

这学期许徐两个班的所有助教活跃性都很低. 发通知改作业自然是合格地完成了, 但没有在群里提供额外的帮助. 许班的课群发生过因为助教不回答提问在群里开喷的事. 我不了解助教义务有哪些范围, 对此事没有什么说的.

②

~~23年秋的时候我会尽可能申请这门课的助教.~~ 可惜了, 没申到.

·

资源

图论导引 习题解答.pdf

自己编写的一份教材习题解答 (外加一些对书上知识的讲解) , 希望能够帮助到有需要的同学. 把之前用word写的那个弱智版本撤了下来, 工具换成了latex, 视觉效果应该会好不少. 由于时间有限, 只改编完了1, 2, 4, 5, 6这五章, 以及附录中关于归纳原理的一部分. 之后我会尽量抽时间完成剩下的内容. 如果发现解答中有严重的知识错误, 或者对这份解答有其它意见或建议, 欢迎联系 eastwind@mail.ustc.edu.cn

注意: 分享此解答的目的在于帮助想要深入学习的同学获得更好的反馈, 避免 "做了题但没有答案" 的处境 ~~(也避免某些申必助教在作业答案里写伪证误导学生)~~ . 请不要抄这里面的题解以应付你的课堂作业!

今年期末出的什么鬼题，xhl老b登你还我GPA😭

出分了，看起来一分未调。。。

题比去年难，调得还比去年拉，只能说老登赶紧爆金币吧

1.23 anyway，先放一下我的简明复习提纲（在学校手写的，放假回家敲了 markdown)

复习提纲.pdf

呃啊怎么放寒假了还要写一堆策划书 原地去世

1.25 出分卡在 3.0，难以置信，首先平时分（也就是作业和两次点名）是满的，其次期末卷面预期也在 70+……查卷可能会安排在下学期，也可能没有，但成绩看来是不会修改了。只能解释为期末成绩占比 70% 甚至更多，而且没有调分。

还有一种解释是跟隔壁 xyl 老师班一块儿算总评了。此处就不得不解释一下打 5 分的原因。

图论这门课程对我而言无疑是有趣的，比代数结构有趣多了。但是前后两位老师都讲得非常抽象，图论的数形结合我是一点没听出来在哪里；赵老师还会带着大家一起过一遍算法的实际应用（比如网络流、中国邮递员问题），徐老师讲课甚至难以让人相信他在照本宣科，与 xyl 班同学交流发现许老师才是真正把计算机图论的思维讲到了，包括数学部分和算法部分。我复习的时候看了一遍课本，虽然是把“非空真子集”这简单的五个字用一行半进行另一种表述的屑书，但实际上没有听课那么昏昏欲睡，上课效果如何我也就不多做评价了，大部分到课的同学只有前几周还愿意听。

至于助教工作，中规中矩，复习课上想不起来 \delta^-(v) 是 v 的入度还是出度，姑且认为助教是当时学的好现在忘了。：）

最后补充一下，有一位室友是 xyl 老师班上的，但复习的时候也不知道为什么算有下界的网络流要建立伴随网络。据了解一半的同学学图论算法都是死记硬背，并没有真正理解为什么要这样做。除了课本之外，多查一查 StackExchange  CSDN  博客园 等偏信竞的算法解释可能会比课本上几大页符号好理解一些，能画图解释或者一句话说清楚的当然最好，能给别人讲出所以然来就更好了。

开学去查卷，卷面64总评81，比例中规中矩吧。但是回旋镖把自己扎死了——

算法的具体应用题拿不到分真的太可惜了

就是说证明题做得漂亮也没啥用

虚晃一枪，成绩回来了，感觉无变化……

！了转反，出分一个小时后，成绩从jw系统上消失了，这是怎么惠氏呢，小编也很好奇。

给老师上课一分，助教可爱心善加一分，期末改卷大捞减一分（但是卡绩了）。

徐老师上课纯念书，别管对的错的，念就完了，念完了直接抄到黑板上也不解释，纯纯的摆烂。想听懂的建议去隔壁xyl老师班上。（实际上上过徐老师的代数结构也是这样（大嘘

期末是赵老师负责给分，卡了一堆低分绩，已知班上的期末卷面最高分最后总评只有89。

咱纯纯摆烂，复习那几天感觉学的比一学期学的还多……空了一题，编了一题，最后81。

作业发答案有点略慢，不过最起码有答案还有习题课。个人整理的作业和资料。

这门课非常好玩，应该和数院大佬们修的组合数学是一个味道，(没有机会修了，难过~~）

但是3学分塞了10章，那对不起，只能过滤思想，充实算法和记忆了~~

和随机过程是我最喜欢的课，只是课程多，没能好好玩。

3.7，有点意外，童鞋们都好厉害！！！

这门课(完整的1~11章)真的想学好绝不止3学分，至少4~5学分，

但是试卷的题量是按5学分出的，导致干完1~4简单题和第5题必要性后，

累了，肝不动了，水完最后一题后，开始背书和摸鱼。

5,6都不简单，但是干完要20~30min。

第7题分类讨论写作业的时候写对了，考试没肝出来。

第8题课本原题，徐班没布置，不知道许班布置了没，要求用最大流-最小截定理证明覆盖数=匹配数，

也有童鞋直接按匹配那一章的证法背了，估计也给满了（没背住，手推，没推完）

印象很深的一句话：“其实大多数我们做不出来题目，是因为想象不出来它的样子”。

个人觉得徐老师人挺好的，作业少，也会把证明时的一些注意点告诉我们，

老师刚带这门课不久，精力也有限，祝老师的课越来越好吧

PS1：寒假想着实现书上的图论算法，但是没能，一个都有没有。

PS2：现在有chatGPT了，徐老师不必再在图论课上让我们自问"现在，大三保研，大学毕业后有没有10W行的代码量了"，(*￣︶￣)(*￣︶￣)

这门课目测是我这两年以来得到的最低分,这当然有自己的原因,但还是得说一句,老师有点杀,目前来看徐老师的风格就是念课本抄课本,其代数结构,图论,以及22春的离散数学风格均是如此,另外不调分或者调分力度很小,反正这个3.3是让我很吃亏的,不过嘛,绩点够用就行,能学到东西才是最好的,这门分数最低的课却恰恰是我到计科以来觉得最有意思的课.

这篇评课主要是来分享一下去年考试的题目,由于本人分很低,合理怀疑是某些题看错了,题目仅供参考~

1.邮差问题,用最小生成树法求解,分两问,先求最小树,再求最小开销
2.证明连通图中两个最长轨道必有交点
3.排课表问题,就是边着色(匹配数)问题,也分两问,第一问求课时,第二问求教室数
4.证明两最大匹配的对称差要么是轨道,要么是偶圈
5.一个作业题,证明2-连通图中存在两相邻点,删去这两点依然连通
6.证明顶点数目为偶数,且满足任意两不相邻点度数和 大于 v-1 的图中存在哈密顿轨
7.最小可行流算法,分三问,第一问叫设计一个与最大流算法中对应的\hat{l},并证明仍然是可行流;
                       第二问是设计一个最小流算法
                       第三问是求一个给定图的最小流
8.给一个图的关联矩阵,在不画出图的情况下求 是否为欧拉图;是否为哈密顿图;是否为连通图;圈数;(还有几个记不得了),并给出理由
这个题貌似给了一个完全图的关联矩阵,不过也可能是我看错题了.

我开始在许胤龙老师的班上，为了换复变函数换到了这里，非常后悔。个人感觉，这个老师的讲课水平和给分好坏不及许老师的一半，而许老师目前评分8.7分，所以我只能给到4分。

关于讲课。根据topusername，许老师会在证明时结合具体的示例讲解，易于学生理解。而就我自己听的两节课来说，许老师上课思路连贯，对讲授内容熟悉，而且会为学生考虑（比如他告诉我们不必浪费时间预习）。

反观徐宏力，老师上课几乎就是把书上的定理的证明过程边读边抄到黑板上。他喜欢抄几行就问学生“课本为什么要这样写”，而且要停下来等学生回答。而大部分学生都是图论的初学者，怎么可能这么快回答？于是上课过程非常不连贯，这导致本班的上课进度明显慢于许老师的班。如果老师认为课本的证明过程的某一步值得注意，应该直接告诉学生，而不是尝试让学生发现。徐老师很喜欢告诉我们，他自己在阅读某一个定理的证明时感到困惑。我认为老师有义务在授课前充分理解这门课的内容，如果老师认为某一步推导不容易理解，应该尝试向学生解释，最好像许老师那样结合示例解释，而不是把自己的困惑分享给学生。徐宏力只讲定义、引理、定理、推论，几乎不碰课本的例题。徐宏力上课说的与课程有关的内容可谓是课本内容的真子集，听他的课不如看书自学，而且由于徐宏力从不点名，你甚至可以到许老师班旁听。

关于给分。本来我不认为给分很差，今天（2022-02-20）跟许老师班的学生交流后才知道，徐宏力其实是给分杀手。根据非常不完全的统计：在许老师班上，甲4题不会总评91，乙3题不会总评92，丙2题不会总评89，丁所有题都写满了总评94；在徐宏力班上，甲所有题都写了总评90，乙所有题都写了总评84。虽然认为会写的题不一定都能写对，但考场上对试题难度的感受和自己的做题体验多少能反映答卷的正确率。可见，徐宏力的给分远不如许老师。虽然在考试题目简单的时候，许老师的班评卷也非常严苛，但许老师至少知道在试题困难的时候放松评卷尺度，并且适当调整分数。可是徐宏力似乎仍然以试题简单时的标准评卷和给分，实在是冷酷无情。

综上，能换走尽量换走。如果换不走，建议自学或到隔壁班蹭课，并且祈祷考试简单。

这门课给我留下了极大的emotional damage，纵然因为他这学期绩点爆炸直降0.1我也不会重修这门课。

老师上课讲得很细致很用心，和隔壁班相比速度慢一些，讲授的内容也少一些。从近几年的期末考试趋势来看，这门课的期末似乎变得简单了一些？但还是抵不住菜鸡真的学不懂啊，一个人一只笔，四道作业写一天，我最慢的一次从周五晚上写到了周日上午QAQ。期末的话还是多看看概念和书上的证明吧（老生常谈但有用（（其实我感觉调分力度不是很大，可能是因为今年jwc搞的新花样♂

切记计科大二上期末会很紧张，实验实在不行就摆烂吧ww，我用了两周写各种实验，选修课论文和期末考试，ics的bonus（再骂一句倒霉ics），最后剩了两周复习期末，天真的我以为就像淑芬一样能刷完题复习完，却忘了那时候淑芬是最后一门而不是现在的八天考六科，最后实在是复习不完喜提图论爆炸，希望大家不要有这样的快乐生活。

我是22秋图论班的学生。上课徐的水平实在不敢评价，当然如果上课就是把课本在黑板抄一遍再念一遍也叫教书那确实，和许老师云泥之别。先把图论的道理弄懂，许老师带的蛮好的，你再加一个念书的干什么(巧了两人都姓xu）

不过好在作业不多，而且大部分人之后感觉用不到这玩意

课去的不多，主要内容是图的基本性质、树、环路，二分图匹配，连通图和最大流最小割，感觉作为思想体操还是挺有意思的。