图论与复杂网络
点与线两样东西，足以描述交通、社交、电网、蛋白质、论文引用。图论给算法，复杂网络给统计规律。
这个模块讲什么
竞赛里凡是「选址、路径、调度、传播、影响力」的题目，剥开外壳基本都是图问题。这个模块前半段是能直接拿去用的经典算法（最短路、最小生成树、最大流、匹配），后半段是理解真实网络为什么长成那样的模型（小世界、无标度、社区结构），最后落到网络上的动力学——传播、同步、级联失效。
8专题
32实验台
专题列表
每个专题是一个独立页面，页内按实验台组织。下面列出的是每一页会做的实验。
3.1
图的基本量
已上线度、路径、连通分量、二分性。先把词汇和直觉建立起来，后面的算法才不是符号游戏。
01画一张图鼠标加点连边，实时显示度序列、连通分量、是否二分
02邻接矩阵与幂矩阵 Aᵏ 的第 (i,j) 项就是长度 k 的路径条数——并排验证
03图的布局力导向、圆周、分层三种布局切换，说明「同一张图可以长得很不一样」
3.2
经典图算法
已上线BFS、Dijkstra、Kruskal、Ford–Fulkerson、匈牙利算法。一步一步放慢演示，看算法为什么正确。
01广度与深度优先单步执行，队列与栈的内容同屏显示
02最短路标记已定点、松弛边；加一条负权边看 Dijkstra 怎么出错
03最小生成树两种贪心并排跑，最终树相同但过程完全不同
04最大流最小割找增广路、更新残量网络，最后高亮那条最小割
05二分图匹配增广路径找匹配，对应到「任务指派」的实际问题
3.3
网络生成模型
已上线为什么真实网络既不是规则格子也不是完全随机？ER、WS、BA 三个模型各解释了一部分。
01ER 随机图调连接概率，看巨片涌现与泊松度分布
02WS 小世界重连概率从 0 到 1，聚类系数与平均路径长度一起画出那张著名的图
03BA 无标度优先连接长出枢纽节点，度分布在双对数坐标下成直线
04三者对比同样的节点数与边数，三种模型的度分布、聚类、路径长度同屏比较
3.4
中心性与社区
已上线谁最重要？怎么把一张网切成几块？这两个问题的答案不唯一，取决于你怎么定义「重要」和「块」。
01五种中心性度、介数、接近、特征向量、PageRank 在同一张图上并排上色，排名差异一目了然
02PageRank 迭代看分数怎么在迭代中重新分配直到收敛，阻尼系数的作用
03模块度与社区发现Louvain 逐层合并，模块度 Q 随之上升
04中心性与攻击随机删点 vs 按中心性删点，网络崩解速度差几倍
3.5
网络上的动力学
已上线结构决定过程。同样的传播规则，放在小世界与无标度网络上，结果完全不同。
01网络上的 SIR在三种网络上跑同一组参数，比较峰值时间与总感染规模
02传播阈值无标度网络的阈值为什么趋近于零
03同步耦合强度一过临界值，一群振子突然同步
04级联失效一个节点过载转移负荷，连锁反应扫过整张电网
3.6
局部结构：模体与聚集
已上线两个人有共同好友，他们认识的概率就高得多。三角形、k-核、同配性——网络的性格藏在这些局部小图案里。
01三角闭合按共同好友数逐条加边，看聚集系数怎么一路爬上去
02模体统计把所有三节点子图数一遍，和随机零模型比出哪种显著超额
03k-核分解一层层剥掉低度节点，剩下的核心就是网络最结实的部分
04同配还是异配社交网喜欢强强联手，技术网喜欢强弱搭配——一个相关系数说清
3.7
空间网络与路网
已上线现实的网大多画在地图上：修一条边要花钱，走一条边要花时间。加上空间约束以后，小世界和无标度就不那么容易出现了。
01空间随机图按距离衰减的概率连边，看度分布与聚集系数怎么跟着变
02A* 与启发式搜索同一张路网上 Dijkstra 与 A* 各自访问了多少个节点
03设施选址p-中位与 p-中心两种目标，选出来的点位完全不一样
04修路的代价与收益每加一条边都要钱：效率、鲁棒性和造价之间怎么权衡
3.8
二分图与匹配市场
已上线学生与学校、医生与医院、乘客与司机，都是两边配对的问题。稳定匹配算法保证没有任何一对想私下反悔。
01稳定婚配Gale–Shapley 一轮轮求婚，看谁先出手谁占便宜
02最小费用流把指派问题写成网络流，在图上看成本怎么一点点降下来
03二分图投影把"演员—电影"投影成"演员—演员"，投影会凭空造出多少三角形
04推荐里的二分图用户—物品二分图上的物质扩散，最简单的推荐算法