美赛BOOM数学建模2-1图论基本概念

注明：本文根据数学建模BOOM网课简单整理，自用

图论基本概念

❑ 图的定义

• 数学建模中的“图”，是根据实际问题简化而来的模型。

• 对于平面上的n个点，把其中一些点用直线或曲线连起来，不考虑所画点的位置和所画直线或曲线的长度，这样形成的关系称为“图”

❑ 示例

• 假设用点表示城市,现有v1, v2, … v5共5个城市，点与点之间的连线表示城市间有天然气管道

• 图论中，这些点称为顶点，连线称为边

• 边上标的数字，实际意义是该条管道长度，称为边的权重（权重和线段画出来的长度无关）

• 同样的，连线也可以表示路径、权重表示路径长度等等关系

❑ 注意事项

• 画出来的图中，顶点位置随意，边的性状和长短随意

• 图的本质，就是从实际问题中抽象出来的顶点和边的关系

• 本示例的图，城市1到2的边，可以画作直线箭头，而现实中从1到2的道路可能是经过了360°托马斯回旋的曲线！只要用权重表示出其长度即可

• 而且权重也不仅仅可用来表示“长度”，也可用来表示费用、损耗、时间等等（图是根据题目而定的）

❑ 图的种类

• 本示例中的边代表天然气管道，是有方向的，边是单向箭头，构成的图称为有向图

• 如果讨论城市间道路的话，是双向的，构成的图称为无向图，连线即可，不需要画箭头

❑ 图得出邻接矩阵

• 邻接矩阵是表示顶点间关系的矩阵

• 邻接矩阵𝑊中第𝑖行第𝑗列的元素：

• 根据题目，画出图；根据图，写出邻接矩阵，进而进行各种计算

• 数学建模过程中，使用矩阵参与运算

• 除了邻接矩阵，图还可以用邻接表来表示（数模中一般用不到）