图论的发展及其在现实生活中的几个应用
华为4g手机-
菏泽学院本科生毕业设计（论文）
图论的发展及其在生活中的应用
数学与应用数学
张佳丽
指导教师
刘秀丽
摘要
主要介绍了图论的起源与发展及其生活中的若干应用，如：渡河问题、旅游推销员问题、
最
小生成树问题、四色问题、安排问题、中国邮递员问题。同时也涉及到了几种在图论中
应用比较广
泛的方法，如：最邻近法、求最小生成树的方法、求最优路线的方法等。
关键词
图论
生活
问题
应用
Graph Theory Development and the
Application in Life
Mathematics and
applied mathematics
Zhang Jiali
Tutor
Liu Xiuli
Abstract
This
paper
mainly
introduces
the
origin
and
development
of
graph
theory
and
its
several
applications in our life, such as:
crossing river problem, traveling salesman
problem, minimum spanning
tree
problem,
four
color
problem
，
arrangement
problem
，
Chinese
postman
problem
．
It
also
researches
several methods that are more widely
applied in graph theory, for example:
the method of
most
neighboring,
the method of
solving the
minimum spanning
tree
，
the method of the best
route
，
and so
on
．
Key
words
graph
theory
life
problem
application
引言
图论是一门古老的学科，是数学
中有广泛应用的一个分支，与其他的数学分支，如
群论、矩阵论、概率论、拓扑学、数分
析等有着密切的联系．图论中以图为研究对象，
图形中我们用点表示对象，两点之间的连
线表示对象之间的某种特定的关系．事实上，
任何一个包含了二元关系的系统都可以用图
论来模拟．而且
,
图论能把纷杂的信息变的
有序、直观、清晰．由于我们感兴趣的是两对象之间是否有某种特定关系，所以图形中
两点间连接与否尤为重要，
而图形的位置、
大小、
形状及连接线的曲直长短则无关紧要．
图论在自
然科学、社会科学等各个领域都有广泛的应用．随着科学的发展，以及生
产管理、军事、
交通运输等方面提出了大量实际的需要，图论的理论及其应用研究得到
飞速发展。
从
20
世纪
50
年代以后，
由于计算机的迅速发展，
有力地
推动了图论的发展，
加速了图论向各个学科的渗透，尤其是网络理论的建立，图论与线性
规划、动态规划等
优化理论和方法互相渗透。同时，计算机的发展使图论成为数学领域中
发展最快的分支
之一．
1
张佳丽：图论的发展及其在生活中的应用
1
图论的起源与发展
1
．
1
图论的起源
[1]
1736
年是图论的历史元年．
这一年，
欧拉
（
L
•
Euler
）
研究了哥尼斯堡
（
K
ö
nigsberg
）
七桥问题，并发表了关于图论的首篇文章．欧拉也因此被称为图论之父．哥尼斯堡城濒
临蓝色的波罗的海，城中有一条普莱格尔（
Pregel
）河，河的两条支流在这里汇合，然
后横穿全城，流入大海．河水把城市分成
4
块，于是，人们建造了
7
座各具特色的桥，把
哥尼斯堡城连成一体，如图一所示．
早在
18
世纪，这些形态各异的小桥吸
引了众多的游客，他们在陶醉于美丽风光的同
时，不知不觉间，脚下的桥触发了人们的灵
感，一个有趣的问题在居民中传开．
图一
图二
谁能够从两岸
< br>A
，
B
，
C
，
D
四个陆地中的任一个地方出
发一次走遍所有的
7
座桥，而
且每座桥
都无重复的只通过一次？这个问题看起来似乎不难，
谁都乐意用这个问题来测
试一下自己的智力．但是，谁也没有找到一条这样的路线．这个问题极大的刺激了人们
的好奇心，
许多人都热衷于解决这个问题，
然而始终
没有人能够成功．
“七桥问题”
难<
/p>
住了哥尼斯堡城的所有居民．哥尼斯堡城也因“七桥问题”
而出了名．这就是数学史
上著名的七桥问题．
2
菏泽学院本科生毕业设计（论文）
问
题看来并不复杂，但就是谁也解决不了，也说不出所以然来．
1736
< br>年，当时著名
的数学家欧拉仔细研究了这个问题，
他将上
述四块陆地与七座桥间的关系用一个抽象图
形来描述
(
见图二
)
，其中
A
、
B
、
C
、
D
四个陆地分别用四个点来表示，而陆地之间
有桥相
连者则用连接两个点的连线来表示，这样，上述的哥尼斯堡七桥问题就变成了由点
和边
所组成的如下问题：
试求从图中
的任一点出发，不重复的通过每条边一次，最后返回到该点，这样的路
线是否存在？这样
问题就变得简洁明了了，同时问题也变得更一般、更深刻了．这样，
七桥问题就转变为图
论中的一笔画问题．即能不能不重复的一笔画出图二中的这个图
形．
原先人们是要求找出一条不重复的路线，欧拉想，既然成千上万的人都失败了，那
么这样的路线也许根本就不存在．于是，欧拉就想：这样不重复的路线究竟存不存在？<
/p>
由于改变了一下提问的角度，欧拉抓住了问题的实质．最后，欧拉认真考虑了一笔画图
形的结构特征．
欧拉发现，凡是能用一笔
画成的图形，都有这样一个特点：每当画一条线进入中间
的一个点时，还必须画一条线离
开这个点．否则，这个图形就不可能用一笔画出．也就
是说，单独考察图中的任何一点（
起点和终点除外），这个点都应该与偶数条线相连；
如果起点与终点重合，那么，连这个
点也应该与偶数条线相连．
在七桥问题的几何图中，
A
、
B
、
D
三点分别与
3
条线相连，
C
点与
5
条线
相连．连线数
都是奇数条．因此，欧拉断定：一笔画出这个图形是不可能的．也就是说，
不重复地通
过
7
座桥的路线是根本不存
在的！天才的欧拉只用了一步就证明了这个难题，从这里我
们也可以看到图论的强大威力
.
欧拉对七桥问题的研究，是拓扑学研究的先声．
1750
年，欧拉又发现了一个有趣的的现象．欧拉因此得到了后人以他的名
字命名的
“多面体欧拉公式”．正
4
面
体有
4
个顶点、
6
条棱，它的面数加顶点数减去棱数等于
2
；
正
6
面体有
8
个顶点、
12
条棱，它的面数加顶点数减去棱数也等于
2
．接着，欧拉又考察
了正
12
面体、正
24
面体，
发现都有相同的结论．于是继续深入研究这个问题，终于发现
了一个著名的定理：
F
(
面数
)
＋
V
(
顶点数
)
－
E
(
棱数<
/p>
)
＝
2
这个公式证明了多面体只有正四面体、正六面体、正八面体、正十二面体、正二十
面体五种．这个定理成为拓扑学的第一个定理，这个公式被认为开启了数学史上新的一
3
张佳丽：图论的发展及其在生活中的应用
页，促成了拓扑学的发展．
1
．
2
图论的发展
图论的产生和发展经历了
二百多年的历史，大体上可以分为三个阶段：
第一阶段是从<
/p>
1736
年到
19
世纪中叶．
当时的图论问题是盛行的迷宫问题和游戏问
题．<
/p>
最具代表性的工作是著名数学家欧拉于
1736
< br>年解决的哥尼斯堡七桥问题
(
见
1
．
1)
．
第二阶段是从
19
世纪中叶到
1936
年．图论主要研究一些游戏问题
:
迷宫问题、博
弈问题、棋盘上马的行走路线问题等，
[2]
随着对这些问题的深入研究，图论又产生了新
的
一系列问题，例如：连通性、嵌入问题、染色问题、矩阵表示以及网络流等．连通性
是图
论研究的基本问题之一，欧拉路、中国邮路问题、哈密顿问题、树与图的支撑树、
匹配问
题都是连通性的典型问题；地图着色问题即是对无论多么复杂的地图，只需用四
种颜色就
足够将相邻的区域分开．平面图的染色问题是与四色问题紧密相联的．于是产
生了着色问
题即给定一个图，如果要求把所有顶点涂上颜色，使得相邻顶点具有不同的
颜色，问最少
需要几种不同的颜色
?
这个问题叫做图的点着色问题．如果对给
定图的全
部边都涂上颜色，使相邻的边有不同的颜色，问至少需要几种颜色
?
这个问题叫做边的
着色问题，边的着色问题可以转
化为点着色问题．由这些问题人们逐渐丰富并发展了图
论学科知识．
同时出现了以图为工具去解决其他领域中一些问题的成果．
1847
年德国的
克希霍夫将树的概念和理论应用于工程技术的电网路方程组的研究．<
/p>
1936
年匈牙利的数
学家哥尼格写出了
第一本图论专著《有限图与无限图的理论》
．标志着图论成为了一门
独立学科．
第三阶段是
1936
年以后
.
由于生产管理、军事、交通运
输、计算机和通讯网路等方
面大量实际问题的出现，大大促进了图论的发展．特别是电子
计算机的大量应用，使大
规模问题的求解成为可能．实际问题如电网络、交通网络、电路
设计、数据结构以及社
会科学中的问题所涉及到的图形都很复杂的，
需要计算机的帮助才有可能进行分析和解
决．目前，图论在物理、化学、运筹学、计
算机科学、电子学、信息论、控制论、网络
理论、社会科学及经济管理等几乎所有学科领
域中都有应用．
2
图论在生活中几种应用
2
．
1
渡河问题
2
．
1
．
1
基本理论
定义
2.1
[3]
有向图：一个有向
图是一个有序的二元组
V
,
E
，记作
D
，其中
4
菏泽学院本科生毕业设计（论文）
（
1
）
V
称为顶点集，其元素称为顶点或结点．
（
2
）
E
为边集，它是笛卡尔积
V
V
的多重子集，其元素称为有向边，简称边．
2
．
1
．
2
应用举例
例
[4]
（渡河问题）
一个摆渡人要把一只
狼，一只羊和一捆菜运过河去，由于船很
小，每次摆渡人至多只能带一样东西．另外，如
果人不在旁时，狼就要吃羊，羊就要吃
菜．问这个人怎样才能安全的将它们运过河去？<
/p>
解
用
F
表示摆渡人，
W
表示狼，
S
表示羊，
C
表示菜
若用
F
W
S
C
表示人和其他三样东
西在河的原岸的状态，
这样原岸全部可能出现的状态
为以下
16
种：
FWSC
FWS
FWC
FSC
WSC
FW
FS
FC
WS
WC
SC
F
W
S
C
表示原
岸什么也没有，即人、狼、羊、菜都运到河对岸了
根据题意，
我们知道这
16
种情况中有
6
种是不允许的，它们是
WSC
、
FW
、
FC
、
WS
、
SC
、
F
，如
FC
表示人和菜在原岸
而狼和羊在对岸，这当然是不允许的．因此，
允许出现的情况只有
10
种．以这
10
种状态为结点，以
摆渡前原岸的一种状态与摆渡一
次后出现在原岸的状态所对应的结点之间的连线为边，作
有向图
2.1
：
C
FSC
S
FS
< br>FWSC
WC
FWC
Φ
W
图
2.1
FSW
上图给出了两种方案，方案为
上图中从
FWSC
到
的不同的基本通路：
⑴
FW
SC
WC
FWC
C
FSC
S
FS
⑵
FWSC
WC
FWC
W
FWS
S
FS
．
它们的长度均为
7
故摆渡人只需摆渡
7
次就能将它们全部运到对岸，<
/p>
并且羊和菜完
好无损．
5
张佳丽：图论的发展及其在生活中的应用
2
．
2
旅行推销员问题
该问题是说：
“给定
n
个城市和它们之间的距离，问如何设
计一条路线，使得一个
推销员从他所在的城市出发途经其余
n<
/p>
1
个城市刚好一次，
< br>最后回到原驻地并使得行程
最短
[5]
< br>？”
2
．
2
．
1
基本理论
定义
2.2
[6]
< br>给定图
G
V
< br>,
E
（
G
为无向图或有向图）
，设
W
：
E
R
（
R
为实数
集）
，对
G
中任意的边
e
<
/p>
v
i
,
v
j
(
G
为有向图时，
< br>e
v
i
,
v
j
)
，
设
W
e
<
/p>
w
ij
，称实
数
w
ij
为边
e
上的权，并将
w
ij
标注在边
e
上，称
G
为带权图，此时常将带权图
G
记作
V
,
E
,
< br>W
．设
G
G
，称
最邻近法
[7]
e
E
G
W
e
为
G
<
/p>
的权，记作
W
G
，即
W
G
=
e
E
G
W
e
< br>
．
(1)
< br>由任意选择的结点开始，找与该点最近（即权最小）的点，形成有一条边的初
始路
径．
(2)
设
X
表示最新加到这条路上的结点，从不在路上的所有结点中选一个与
< br>X
最靠
近的结点，
把连接
X
与这一结点的边加到这条路上，
重复这一步
，
直到
G
中所有结点包
含在路上．
(3)
将连接起
始点与最后加入的结点之间的边加到这条路上，就得到一个圈，即为
问题的近似解．
2
．
2
．
2
应用举例
例
[8]
某流动售票员居住在
A
城，为推销货物他要访问
B
、
C
、
D
城后返回
A
城，
若该四城间的距离如下图
2.2
所示，找出完成该访问
的最短路线．
B
11
A
13
8
C
< br>6
D
图
2.2
7
16
解
步骤如下图①—④
6
菏泽学院本科生毕业设计（论文）
B
A
C
8
D
①
B
A
C
8
6
D
②
< br>B
7
A
C
8
6
D
③
B
11
A<
/p>
C
8
6
D
④
7
最短距离为：
8+6+7+11=32
．
2
．
3
最小生成树
2
．
3
．
1
基本理论
定义
2.3.1
[9]
设
G
V
,
E
，
G
V
,
E
为两个图（同为无向图或同为有
向图）
，
7
张佳丽：图论的发展及其在生活中的应用
若
V
V
且
E
<
/p>
E
，则称
G
<
/p>
是
G
的子图，
G
为
G
的母图
，记作
G
G
．又若
V
V
或，
E
E
则称
G<
/p>
为
G
的真子图
，若
V
V
，则称
G
为
G
的生成子图．
定义
2.3.2
[10]
不含圈的连通图称为树．
定义
2.3.3
[11]
如果
T
是
G
的一个生成子图而且又是一棵树，则称
T
是图
G
的一棵
< br>生树．
定义
2.3.4
[12]
设无向连通带权图
G
V
,
E
,
W
，
T
是
G
的一棵生成树，
T
的各边权
之和称为
T
的权．<
/p>
G
的所有生成树中，权最小的生成树称为
G
的最小生成树．
⑴破圈法
[13]
< br>在
G
中任取一个圈，
去掉其中一
条边，
然后再取一个圈，
再去掉这个圈中的一条边，
如此继续下去，最后得到的连通图的无圈的生成子图就是
G
的一棵生成树．
⑵用破圈法求带权的最小生成树的方法
在赋权图
G
中任取一个圈，
然后去掉
这个圈中权最大的边，
如此继续进行直到
G
中
不再有圈时为止，这时剩下的边组成的子图就是最小树．
[14]
2
．
3
．
2
应用举例
旅游线路中的最短问题
对于旅客
来说，要求在最短的时间内用最少的钱来旅游
最多的景点，考虑到无论采取哪种方案，在
门票的花费均相同且路费在速度恒定的情况
下可由路程的多少来求得，从而把问题转化为
求最短的旅游路线的问题．
[15]
例
[16]
公园的路径系统图如图
2.3
，其中
S
为入口，
T
为出口，
A
，
B
，
C
，
D
，
E
为五个景点，现求如何能使观光旅游车从入口
S
到出口
T
所经过的距离最短．
A
2
S
4
C
5
1
2
D
7
4
B
3
4
7
E
5
1
T
< br>图
2.3
解
用破圈法求带权的最小生成树的
方法求解，求解步骤如下图①—⑥
8
菏泽学院本科生毕业设计（论文）
A
2
S
4
C
1
2
D
7
4
B
3
4
7
E
1
< br>T
5
①
A
2
S
1
C
2
D
7
4
B
3
4
7
E
< br>1
T
5
②
A
2
S
1
C
4
2
B
3
4
D
5
1
T
< br>7
E
③
A
2
S
1
C
④
9
D
2
B
3
7
E
4
5
1
T