如：
乙
为了反映城市之间有没有航
班，我们可用右图表示。甲城与 乙城，乙城与丙城有飞机到达， 而甲、丙两城没有直飞航班。
对于工作分配问题，我们可 能用点表示工人与需要完成的工 作，点间连线表示每个工人可以
甲 丙
工人
甲 乙
工作 A
B
胜任哪些工作如右图所示。
丙
C
Ｄ
4
图的定义：
所谓图，就是顶点（简称点）和一些点之间的连线（不带箭头或者 带箭头）所组成的集合。
v v 一条联结
和
i1
in的链，记作
vi1 ,vi2 , 。 ,vin
9
（2）开链和闭链：如果 vi1 ，vi则n 该链称为开链；如果
称为闭链（或称为圈）。
v，i1 =则v该in 链
（3）简单链和初等链：如链内所含的边均不相同，称之为简单链；如 链内所含的点均不相同，称之为初等链。
如：
Ｖ1
e4
有向图D中的链不一定是路，因为有向图的链可能存在和链的方向
（4）基础图和路：若把一个有向图D的方向去掉，即每一弧都用相应 得无向边代替，所得到的一个无向图，称为该有向图D的基础图， 记为G（D）；
基础图G（D）中的链（或圈）恢复无向边的方向后，称为有向图
D的链（或圈）。
若交替序列 vi1 ,ai1 ,vi2 ,ai2 , 是,有vin向-1 ,a图in-G1 ,v的in一条链，且满
Ｖ4
e5
v1,v2 ,v3,v4 ,v5 ,v3,v6 ,v7
是简单链，
v1,v2 ,v3,v6 ,v7
e1 e2
Ｖ2
e7
Ｖ6
e3
Ｖ5 是初等链，
e6
Ｖ3
e9
e8
Ｖ7
v1,v2 ,v3,v4 ,v1
是初等圈，
v4 ,v1,v2 ,v3,v5 ,v7 ,v6 ,v3,v4
是简单圈，
10
6
如有向图：D= V,A
Ｖ3 a2
Ｖ1
a3
a1
Ｖ2
V=v1,v2 ,v3 ,v4 ,v5 ,v6 ,v7
a8
Ｖ5
Ｖ7
a10
A=a1,a2,a3, ,a11
a11
a6 a4
a9 Ｖ6
a7
a1= v1,v2 ,a2 = v1,v3 ,a3= v3,v2 , a4 = v3,v4 ,a5= v2,v4 ,a6= v4,v5 ,
A
置的解题方法”的论文，解决了著名的哥尼斯
堡七桥问题．
C
D
欧拉证明了上述图形一笔划是不可能的，
因为图中每一个点都只和奇数条线相关联．
B
他的结论是：图形能一笔画的充要条件是图形的奇顶点（连接
奇数条线的顶点）的个数为零
3
二、图的定义
在自然界和人类的实际生活中，常用点和点与点之间的联线
所构成的图，来反映某些研究对象和对象之间的某种特定的关系。
（2）端点和关联边：若 e= vi ,vj， 则E称顶点
是e v的i ,v关j 联边。
是 v的i ,v端j 点，e
（3）相邻点和相邻边：若顶点 v和i v与j 同一条边相关联，则称点 和vi
为v j相邻点；若边 和ei 有e一j 个共同的端点，则称其为相邻边。
（4）环和多重边：若边的两个端点属同一顶点，则称该边为环；若两个
V仍表示有向图D的非空的顶点集合，A 表示D的弧集合。一条方向从
指向 vi的弧记v为j
。a= vi,vj
5
如无向图： G=V,E
Ｖ1
e5
Ｖ4
e7
e1
Ｖ2
e2
e6
e3
Ｖ3
e4
V= v1,v2 ,v3,v4 E=e1,e2,e3,e4,e5,e6 ,e7
e1=v1,v2 ,e2 =v1,v2 ,e3=v2,v3 , e4 =v3,v4 ,e5=v1,v4 ,e6=v1,v3 ,e7 =v4,v4
端点之间多于一条边，则称这些边为多重边。
（5）多重图和简单图：含多重边的图称为多重图，无环也无多重边的图 称为简单图。
8
（6）次和孤立点：与点关联的边的条数，称为点的次，记作 d(v；) 次 数为零的点为孤立点。
（7）悬挂点和悬挂边：次为1的点称为悬挂点；悬挂点的关联边称为 悬挂边。
（8）奇点和偶点：次为奇数的点称为奇点；次为偶数的点为偶点。
a5
Ｖ4
a7 = v4,v6 ,a8= v5,v3 , a9= v5,v4 , a10 = v5,v6 a11= v6,v7
7
三、基本概念
点和边的相关概念：
（1）顶点数和边数：给定图 G=V，,E集 合V的元素的个数，称为图G的顶点
数，记作 ；集p(G合) E的元素的个数，称为图G的边数，记作 。 q(G)
第5章 图与网络分析
图论的基本概念 最小支撑树 最短路问题
图论是由瑞士数学家欧拉（Euler）于1736年创始的，当时有一个
世界难题，叫“哥尼斯堡七桥问题” 。
哥尼斯堡城中有一条河，叫普雷格尔河，河中有两个岛，河上有七
座桥，如图所示。当时那里的居民
足
aik =，v即ik链,vi中k+1 每一条弧的箭头方向都和链的方向一致，那么
该链称为有向图D 的一条从 到 的路，v简i1 记vin μ=vi1 ,vi2 , 。,又vi若n-1 ,vin ，则称μ为v图i1 =Dv中in 的回路。
➢ 对无向图G来说，链和路（闭链和回路）这两个概念是一致的。但
热衷于这样的问题：
A
一个散步者能否走过七座桥，
但每座桥只走过一次，最后回到
C
D
出发点。
B
2
欧拉用A、B、C、D四点表 示河的两岸和小岛，用两点间的 联线表示桥，如右下图所示，该 问题可归结为：
能否从某一点出发，一笔画 出这个图形，最后回到出发点而 不重复？即一笔画问题。
A
C
D
B
欧拉在1786年发表了题为“依据几何位
为区别起见，不带箭头的连线称为边， 带箭头的连线称为弧。
➢ 如果一个图是由点和边所构成的，则称之为无向图（也简称为图），
记作 G=V，,E其 中V表示图G的非空的顶点集合，E表示G的边的集合。
连接顶点vi和 v的j 边记为
e；= vi ,v j
➢ 如果一个图是由点和弧所构成的，则称之为有向图，记作 D=V，,A其 中
定理1 图 G=V中,E，所有顶点的次之和等于所有边数的2倍，
即 d(v)=2q vV
链的概念：
（1）给定一个图 G=V，,E一 个点、边的交错序列
vi1 ,ei1 ,vi2 ,ei2 , ,vin-1 ,ein-1 ,vin ，
如果满足 eit = vit ,vit+1 , t=1, 2, n-。1这样的序列称为