图的鹅卵石游戏:图论、数论和最优化的融合  

作　　者：Glenn Hurlbert Franklin Kenter 徐鑫(译) 梁燕姣(校) 

机构地区：[1]弗吉尼亚联邦大学数学与应用数学系 [2]美国海军学院 [3]不详

出　　处：《数学译林》2022年第3期216-234,共19页MATHEMATICS

摘　　要：1.引言有很多图论的研究主题可以统一到“在图上移动物体”的框架之下。例如,在网络优化中,人们将包裹从某些供应顶点转移到其他有需求的顶点上,其中每条边都赋予每个包裹运输费用,尝试找到方案使得总费用最低.在网络流中,根据每条边的容量限制以及路径上顶点的流量守恒要求,尝试寻求从源点到汇点的最大流量.在各类追捕和逃逸问题中,警察和盗贼在边上依次移动,警察追击到盗贼即完成抓捕,人们研究在保证完成任务的前提下需要警察的最少数量.

关 键 词：最大流量 容量限制 最优化 图论 包裹运输 网络优化 移动物体 流量守恒 

分 类 号：G634.6[文化科学—教育学]