图论
研究由顶点和边构成的抽象网络:连通性与路径刻画网络结构,染色与匹配处理资源分配,网络优化在图上求解最短路径、生成树与最大流,是算法与工程的数学底座。
3 个分节9 个概念
§ 01
图的基本概念
图是最通用的关系模型:顶点代表对象、边代表二元关系,树是最简连通结构,连通性刻画网络能否互达。
§ 02
染色与匹配
染色为相邻对象分配不同标签,匹配为对象两两配对,二者都有漂亮的极值定理与丰富的应用(调度、登记、时间表编排)。
§ 03
网络优化
在图(网络)上求解极值问题:最短路径、最省连接、最大吞吐,这些算法是路由、物流与运筹学的基础设施。