第２Ｉ５卷第４期 ｌ０年ｌ２月 沧州师范专科学校学报 Ｊｏｕｍａｌ ｏｆ 咖Ｔｅａｃｈｅｒｓ’Ｃｏｌｌｅｇｅ Ｖｏ１．２６，Ｎｏ．４ Ｄｅｃ． Ｄ１０
数学建模中的图论方法
艾素梅 ，魏文宏 ，刘力
（１．沧州师范学院数学系，河北沧州０５１００１；２．沧州市第一中学，河北沧州０６１０３０）
摘要：数学建模中图论方法是一种独特的方法。图论建模是指对一些客观事物进行抽象、化简，并用图来描述事物特
征及内在联系的过程。例举了三个实际问题并用图论方法给予解决。 关键词：数学建模；图论；图论方法
中图分类号：（）２４２．１ 文献标识码：Ａ 文章编号：１０３８— （ ｌ０）ｏ４一Ｏ３９８一（Ｉ２
图论建模是指对一些客观事物进行抽象、化简，并用图来
描述事物特征及内在联系的过程。建立图论模型的目的和 建立其它的数学模型一样，都是为了简化问题，突出要点，以
便更深入地研究问题的本质；它的求解目标可以是最优化问
题，也可以是存在性或是构造性问题；并且，和几何模型、运筹
学模型一样，在建立图论模型的过程中，也需要用到集合、映
射、函数等基本的数学概念和工具；但图论模型和其它模型在
它们的研究方法上又有着很大的不同，例如我们可以运用典
型的图论算法来对图论模型进行求解，或是根据图论的基本
理论来分析图论模型的性质，这些特殊的算法和理论都是其 它模型所不具备的，而且在其它模型中，能用类似于图这种直
观的结构来描述的也很少。 ｌ
ｌ最短路问题
１．１定义
定义ｌ设Ｐ（ｕ， ）是赋权图Ｇ＝（ ，Ｅ，Ｆ）中从点ｕ到
”的路径，用Ｅ（Ｐ）表示路径Ｐ（ｕ， ）中全部边的集合，记Ｆ
（Ｐ）＝∑Ｆ（ｅ），则称，（Ｐ）为路径Ｐ（ｕ， ）的权或长度（距 ∈ｒｆＪ ） 离）。
定义２若Ｐｎ（ ， ）是Ｇ中连接ｕ， 的路径，且对任意
在Ｇ中连接“， 的路径Ｐ（ｕ， ）都有 ’（Ｐ０）≤Ｆ（Ｐ），则称Ｐ０
（“， ）是Ｇ中连接ｕ， 的最短路。 重要性质：若Ｖ０ 。… 是Ｇ中从 到 的最短路，则
各种图论模型及其解答
摘要：
本文用另一种思路重新组织《图论及其应用》相关知识。首先，用通俗化语言阐述了如何对事物间联系的问题进行图论建模；接着从现实例子出发，给出各种典型图论模型，每种图论模型对应于图论一个重要内容；再者，介绍相关知识对上述提到的图论模型涉及的问题进行解答；最后，补充一些图论其他知识，包括图论分支、易混概念。
符号约定：
Q(Question)表示对问题描述，M(Modeling)表示数学建模过程，A(Answer)表示原问题转化为何种图论问题。
一、引言
图论是研究点、线间关系的一门学科，属于应用数学的一部分。现实生活中，凡是涉及到事物间的关系，都可以抽象为图论模型。点表示事物，连线表示事物间的联系。整个求解过程如下：
原问题——>图论建模——>运用图论相关理论求解——>转化为原问题的解
整个过程关键在于图论建模，所谓图论建模，就是明确点表示什么，连线表示什么，原问题转化为图论中的什么问题。存在以下两种情况：
①若事物间联系是可逆的(比如双行道，朋友)，则抽象成无向图
②若事物间联系是不可逆的(比如单行道，状态转化不可逆)，则抽象成有向图
如果需要进一步刻画事物间的联系（比如城市间的距离），就给连线赋一个权值，从而抽象成赋值图。
综上，根据实际问题，可建模成下列图论模型的一种：无向赋权图、有向赋权图、无向非赋权图、有向非赋权图。
例1.宴会定理：任何一宴会中，一定存在两个人有相同的数量朋友
M：点表示人，连线表示当且仅当该两个人是朋友
A：问题转化为任何一个图一定存在两个顶点的度相等
二、图论模型
接下来介绍若干典型的图论模型，每种模型几乎对应于图论的一个重要内容，这些内容将在第三章进行讨论，也就给出了这些模型的解答思路。
2.1 偶图模型 凡涉及两类事物间的联系（即只考虑两类事物间的联系，而不考虑同类事物间的联系），均可抽象成偶图模型。作图时，将两类事物分成两行或者两列。这类模型通常被包含在后续的模型中，但因许多现实问题可抽象成该模型，所以单列出来讨论。
第5章 图论及网络分析模型（2课时）
教学目的
介绍如何使用图的方法建模。
教学难点
根据竞赛图写出其邻接矩阵。
1. 循环比赛的名次
1.1 问题
n 支球队循环比赛，每场只计胜负，没有平局.根据比赛结果排出各
队名次.图（1）给出了6支球队的比赛结果，即1队战胜2、4、5、6队，
而输给了3队；5队战胜3、6队，而输给了1、2、4队等等.
方法1：寻找按箭头方向通过全部顶点的路径.
312456 146325 ……⇒无法排名
方法2：计算得分：1队胜4场，2，3队各胜3场，4，5队各胜2场，6队胜1场.2，
3队，4，5队无法排名.3→2，4→5⇒排名132456合理吗？
用图论的知识可以解决这个问题.
1.2 竞赛图及其性质
循环比赛的结果——竞赛图：每对顶点之间都有一条边相连的有向图. 3个顶点的竞赛图：
名次：{1,2,3} {(1,2,3)}并列
4个顶点的竞赛图：
名次：{1,2,3,4} {2,(1,3,4)} {(1,3,4),2} {(1,2),(3,4)}
{1,2,3,4}?
竞赛图的3种形式：
z 具有唯一的完全路径，如（1）；
z 双向连通图——任一对顶点存在两条有向路径相互连通，如（4）；
z 其他，如（2），（3）.
竞赛图的性质：
必存在完全路径；
若存在唯一的完全路径，则由它确定的顶点顺序与按得分排列的顺序一
致，如（1）.
双向连通竞赛图),(EVG=的名次排序
1. 3模型建立
定义邻接矩阵如下：
⎩⎨⎧
∉∈
=
EvvEvv
a
jiji
ij
,0,1
故（4）的邻接矩阵为
⎥⎥⎥⎥
⎦⎤
⎢⎢⎢⎢
⎣⎡
=
0001100011000110
A
记顶点得分向量为 ，则有 T
nssss),,,(
21"=
T
eAes)1,1,1(,"==
T
Aes)1,1,2,2()1(
==～1级得分向量
T
Ass)2,1,2,3()1()2(
==～2级得分向量
T
s)3,2,3,3()3(
高中数学学习中的数学建模方法
数学建模是一种将数学知识应用于实际问题解决的方法。在高中数学学习中，数学建模方法可以帮助学生将抽象的数学理论与现实问题相结合，提高数学学习的深度和实用性。本文将介绍几种高中数学学习中常用的数学建模方法。
一、函数建模法
函数建模是数学建模中最基本的方法之一，它通过建立函数模型来描述实际问题。在高中数学学习中，常以线性函数、二次函数和指数函数等为基础进行建模。例如，在经济学中，可以使用成本函数和收入函数来描述生产成本和盈利情况，从而帮助分析最优生产量和成本控制等问题。
二、统计建模法
统计建模是数学建模中的另一种重要方法。它通过收集数据并进行统计分析，建立数学模型来描述数据的规律和趋势。在高中数学学习中，统计建模常用于分析一组数据的分布特征、相关性和预测等问题。例如，在生物学中，可以通过统计分析人口数据来研究人口增长趋势和变动规律。
三、优化建模法
优化建模是一种将数学方法应用于寻找最优解的方法。在高中数学学习中，优化建模常用于求解最大值、最小值和最优方案等问题。例如，在物理学中，可以通过建立目标函数和约束条件，应用最优化理论来求解运动路径、能量最优分配等问题。
四、图论建模法
图论建模是数学建模中的一种重要方法，它通过构建图模型来研究问题之间的关系和网络结构。在高中数学学习中，图论建模常用于解决行走问题、网络问题和路径问题等。例如，在计算机科学中，可以通过建立图模型来优化网络传输路径和最短路径等问题。
五、微分方程建模法
微分方程建模是一种将微分方程应用于实际问题的方法。在高中数学学习中，微分方程建模常用于研究变化过程和动力系统等问题。例如，在物理学中，可以通过建立微分方程模型来描述物体的运动和振动特性。
综上所述，高中数学学习中的数学建模方法包括函数建模、统计建模、优化建模、图论建模和微分方程建模等。这些数学建模方法不仅可以帮助学生将数学理论应用于实际问题，还能提高解决问题的能力和思维方式。因此，学生在数学学习中应该积极掌握和运用这些数学建模方法，提升数学学习的实用性和创新性。
