2025秋 课程号：CS270101
- 课程难度：困难
- 作业多少：中等
- 给分好坏：超好
- 收获大小：很多
| 选课类别：计划内与自由选修 | 教学类型：理论课 |
| 课程类别：本科计划内课程 | 开课单位：计算机科学与技术系 |
| 课程层次：专业基础 | 学分：3.0 |
该课程系统介绍图论中的基本概念、基本理论、基本算法及其重要应用。课程中首先介绍了图的基本概念，然后分章详细讨论了图的一些特殊性质及一些特殊图，具体内容包括：树；连通性；Euler图和Hamilton图；平面图；匹配理论；支配集和独立集；着色理论；有向图；网络中的最大流；图的矩阵表示；谱图论；图的稀疏化。在各章还介绍了相应的应用背景，从中体现了将实际问题转化为图论问题的思想和方法。
- 课程难度：困难
- 作业多少：中等
- 给分好坏：超好
- 收获大小：很多
- 难度：困难
- 作业：中等
- 给分：超好
- 收获：很多
先放些可能有用的参考资料
开学时给出的参考书之一：华章数学译丛18-图论导引 原书第2版,（美）（韦斯特）Douglas B. West著.pdf
书后习题参考答案：华章数学18图论导引答案Douglas B.West-Introduction to Graph .pdf
本人中间翘了三次课记的一点听课笔记：图论随笔.zip
H班和其他两个班的区别应该有：
- 多了一场期中，总评比例3:3:4
- 作业交电子版，推荐用latex，我用的模版是这个latex-homework-template-master.zip
- 谱图论、图上随机游走、稀疏化为这门课的
私货特色内容（跟线代、概统、随机过程的内容有联动，但是不算很难） - 与科大教材相同部分的内容有些许改动，比如讲匹配的时候额外介绍了Edmonds开花算法和Horp-craft快速匹配算法，一些记号和名称有细微改动，有些概念和定理省略没讲
我没拿过牌子，老家没有任何竞赛资源，当年自己闭门造车学了些知识，对离散数学的内容比较感兴趣，在这门课上花了很多时间（甚至是这学期翘课最少的一门专业课，其他课我天天翘），克服了不少困难。跟隔壁ICSH相比，如果对理论这一块没有很大的热情，选这门课是会很煎熬的（放弃修读，图论H不是水课！）。
彭老师开学的时候给出了这样的期待：
期中以前比较清闲，我课下还是能花几个小时读一读West，无奈脑子转的实在慢，一杆笔一张纸一道题目想半天，可能还是一个伪证，这时候怼着参考答案看半天才理解这个构造的小巧思。期中考试题目的确有些困难了，而且是周四早八随堂考试，两个小时对困晕的我来说还是太短了，没办法完整地写出来几个题（哪怕乱糊步骤都没什么时间，很仓促），出分后第一次理解什么叫六十分万岁。期中后其他课的作业实验比较繁多，就没有花额外的时间学这门课了，期末前最后一次习题课助教带着我们复习Lecture notes的时候说有可能会降低难度，出几道讲义的定理抛给你证（似乎大数据算法就是这么干的），最后期末考试题目也是放了海，我写完居然还能留下半个小时的余裕，没出卷面分直接提交总评。
中国人往往重视结果而忽略过程，这很容易对认真付出但结果不佳的人造成伤害。程艺老师也说过，成绩是学习的副产物，我深以为然。期中前我尽力做到了老师的要求，虽然期中很惨淡；期中后我很松懈，但期末大概率是远好于惨淡的期中的。如果真心想要做好一门学问，我想还是不要被一个randint(0,100)的数字影响了自己的心态，知道什么可为，知道什么不可为，尽力让自己问心无愧，成为一名有风度的学者，而不是一个死咬着成绩不放的区。
这门课让我见识到了一些很有趣的内容，彭老师的讲课风格也很match，有种梦回淑芬B2🚀课堂的感觉，但是到课人数真的很稀疏啊。
希望未来这门课越来越好吧！
- 课程难度：困难
- 作业多少：中等
- 给分好坏：超好
- 收获大小：很多
- 难度：困难
- 作业：中等
- 给分：超好
- 收获：很多
课程内容正如课程简介上所说的那么多，分为12章节，比普通班增添了随机游走和图的稀疏化两章内容。
老师上课的时候按照自己准备的讲稿讲课，无PPT，不用课本，不点名，讲得非常细致。讲课大体流程是介绍一些图，引入一些定义，然后突然抛出一个定理开始证明，哐哐哐一通证明，发现定理是对的；然后又突然凭空抛出一个定理出来，哐哐哐证明，发现也是对的；重复几次之后就该下课了。虽然说图论属于离散数学，但是这样讲未免也太离散了一点，我听不懂，于是两三周后就不去听课了。抛开离散不谈，老师的讲课内容还是非常丰富的。
虽然老师讲课非常离散，但是每节课都会有一个助教将老师讲的内容整理成pdf讲义发布出来。讲义写的非常细致且有条理（大多数时候），几乎完全覆盖了课上的内容，非常适合拿来自学。（个人建议配合 https://oi-wiki.org/ 食用，这是一个算法竞赛相关网站，部分图论内容在这上面也有介绍。）
作业平均半个月发布一次，一个月收一次，全部线上提交，但是后半学期没有把控好时间导致某一周需要速通一次作业。每一章节平均有3-5道简答题，大部分题目相对简单，但少数题目非常需要脑洞：想到了就非常简单，想不到就完全做不出来。助教批改作业非常宽松，基本上写完就是满分，写“我不会做”也可能满分。作业截止后助教会开相关的习题课，也讲得非常好。
期中考试的难度与作业中的难题相当，但是由1道送分题和5道作业难题组成。助教批改的比较严格。班级在查分前的中位数是60分。查分的时候一个助教说：“彭老师在其它课程的习惯是期中出难题期末出简单，期末的题目基本是人就会做，人均80+。”
期末考试由4道背诵默写讲义和2道作业难题组成（我只背出来了两题半，但考完一问发现其他人全背出来了，难道我不是人）。期末考试后没有查分也不公布，老师和助教火速向jwc提交了成绩并出总评。我在期中60，期末大概率60-的情况下拿到了总评83分，只能说助教已经尽力了。
- 课程难度：困难
- 作业多少：中等
- 给分好坏：超好
- 收获大小：很多
- 难度：困难
- 作业：中等
- 给分：超好
- 收获：很多
期末没给分数，直接出的总评，给分超出预期了，来写个点评。
这门课算是计科英才班理论方向的置课，谱图论、图上随机游走、稀疏化应该是H课特有的私货，虽然很困难，但用线代的角度来理解图论还是挺有趣味的。平时上课没有考勤，我自己完全是看助教写的pdf自学的，绝大多数情况下写的还是很清楚的，只是最后可能有几个证明有点不说人话了。
由于期中考试的题很困难，期末出的相对容易不少，而且有很多是课上讲过的证明，直接变默写了。对于高中接触过信息学/数学竞赛，或者对于图论有兴趣的同学来说，这门课算是这学期计科培养方案的一众史课中为数不多的既有收获，压力也没那么大的好课了。
- 课程难度：困难
- 作业多少：很少
- 给分好坏：一般
- 收获大小：一般
- 难度：困难
- 作业：很少
- 给分：一般
- 收获：一般
这门课算是cs英才班的半个置课吧，想给纠结在理论方向和系统方向做选择的学弟学妹一些建议
先说结论：图论H这门课相比隔壁计算机系统概论H来说很难，非常难，慎选
一是班里面大佬非常多，就我认识的人里面就有蛮多高中数竟信竟拿过牌子的，和这些人一起上课可能会有被碾压的快感🥵
二是相比隔壁计算机系统概论H，同样是H课，体感上这门课给分是没隔壁好的，也没有隔壁的保底机制的，计概H考试占比比较低，只要认真完成实验在顺手卷卷bonus，基本有个3开头的保底绩点，计概H的优秀率也是有逆天的80％，相比之下图论H这边可能显得比较拉了
再说说图论H相比普通班可能的好处：如果你选择图论H，你确实能学到更多更深的东西，彭攀老师还是有资历的，猪脚也比较尽职，平时作业少，上课完全不点名，平时基本不强求你去上课的，在这方面管的比较宽松
最后做个总结：如果你想轻轻松松摆烂拿保底绩点，建议选系统方向去选计概H
如果你想花点时间学的更多更深入，或者你本身水平就比较高，那就选图论H吧
