v4
v6
d(v1)=3 ; d(v2)=5 ;
v7
d(v3)=4 ; d(v4)=4 ; d(v5)=1 ; d(v6)=3; d(v7)=0
v3 v1 v2
其中 v5 为悬挂点， v7 为孤立点。
定理5.1 所有顶点度数之和等于所有边数 的2倍。 证明：因为在计算各个点的度时，每条 边被它的两个端点个用了一次。
能的，因为这个图形中每一个顶点都与奇数条边相 连接，不可能将它一笔画出，这就是古典图论中的 第一个著名问题。 在实际的生产和生活中，人们为了反映事物
之间的关系，常常在纸上用点和线来画出各式各样
的示意图。
图论应用举例

例如，在组织生产中，为完成某项任务，各工序之 间怎样衔接，才能使生产任务完成得既快又好。 一个邮递员送信，要走完他负责投递的全部街道， 完成任务后回到邮局，应该按照怎样的路线走，所 走的路程最短。 各种通信网络的合理架设
定理5.2 在任一图中，奇点的个数必为偶数。 证明：设 V1，V2 分别是图G中奇点和偶点的 集合，由定理5.1 ，有
v 1 V
d (v ) d (v ) d (v ) 2q
v 2 V v V
因为
d (v) 是偶数， d (v)也是偶数，因此
vV
vV1
vV2
C
A
B
D
哥尼斯堡七橋問題可以看成是：对这样一个封闭 的图形，是否可以一笔画完成它并且回到原点
C
A
B
D
数学家欧拉(Euler, 1707-1783) 于1736年严格地证明了上述哥尼斯 堡七桥问题无解，并且由此开创了图论的典型思维方式及论证方式
即能否从某一点开始不重复地一笔画出这个图形，
最终回到原点。欧拉在他的论文中证明了这是不可



交通网络的合理分布等
生 活 中 的 一 些 例 子
台大网路架构图
例5.1 图5.2是我国北京、上海、重庆等十四个城市之间的
铁路交通图，这里用点表示城市，用点与点之间的线表示城 市之间的铁路线。诸如此类还有城市中的市政管道图，民用 航空线图等等。 北京 天津 石家庄 太原 塘沽 济南 青岛
(1,1,1,1) (0,0,0,0)
(1,1,1,0) (0,0,0,1)
(1,1,0,1) (0,0,1,0)
(1,0,1,1) (0,1,0,0)
(1,0,1,0) (0,1,0,1)
(0,1,0,1) (0,1,0,0) (0,0,1,0) (0,0,0,1) (0,0,0,0) (1,0,1,0) (1,0,1,1) (1,1,0,1) (1,1,1,0) (1,1,1,1) 河西=(人,狼,羊,菜) 河东=(人,狼,羊,菜) 将10个顶点分别记为A1, A2, …, A10 ,则渡河问题化为在该 图中求一条从A1到A10的路. 从图中易得到两条路： A1 A6 A3 A7 A2 A8 A5 A10; A1 A6 A3 A9 A4 A8 A5 A10.
1
v
4
v
6
v3
v5
从以上的几个例子可以看出，我们用点和点
之间的线所构成的图，反映实际生产和生活中的
某些特定对象之间的特定关系。通常用 点 表示研 究对象，用 点与点之间的线 表示研究对象之间 的特定关系。由于在一般情况下，图中对象的相 对位置如何，点与点之间线的长短曲直，对于反
映研究对象之间的关系，显的并不重要，因此，
Königsberg (Koenigsberg)
哥尼斯堡，原为东 普鲁士 (Prussia) 首 府，现属俄罗斯(飞 地)，名为加里宁格 勒(Kaliningrad)


哥尼斯堡七桥问題: 要如何走过每座桥 恰一次，再返回出发点？
普瑞格爾河
哥尼斯堡七桥问题
C
A
B
D
哥尼斯堡七桥问题可简化为以下图形 其中的四个顶点都是奇顶点
d (v )也必是偶数，从而V1 中的点数是偶数。
图的连通性： 链：由两两相邻的点及其相关联的边构成的点边序列。
如:v0 ,e1 ,v1 ,e2 ,v2，e3 ,v3 ,…,vn-1 , en ， vn ; v0 ，vn分别
为链的起点和终点 。记作（ v0 ,v1 , v2， ,v3 , …, vn-1 , vn ） 简单链：链中所含的边均不相同； 初等链：链中所含的点均不相同, 也称通路； 圈：若 v0 ≠ vn 则称该链为开链，否则称为闭链或 回路或圈；
端点的度 d(v)：点 v 作为端点的边的个数
奇点：d(v)=奇数；
偶点：d(v) = 偶数； 悬挂点：d(v)=1； 悬挂边：与悬挂点连接的边； 孤立点：d(v)=0； 空图：E = ，无边图
v1
v3
v5
v6
v2
v4
图
5.7
v5
V={v1 , v2 , v3 , v4 , v5 ,v6 , v7 }
v3
v1 v2
v5
v7
v6
图 5.5 v4
图的基本概念
一 个 图 G 或 有 向 图 D 中 的 点 数 ， 记 作 P(G) 或
P(D)，简记作P；边数或者弧数，记作q(G)或者
q(D)，简记作q 。 如果边[vi ,vj]E ，那么称vi , vj 是边的端点， 或者vi ,vj 是相邻的。如果一个图G中，一条边的 两个端点是相同的，那么称为这条边是环，如图
图的矩阵表示
1. 邻接矩阵 Adjacency matrix 表示图中两点之间的相互关系 两点之间有弧或边的，用1表示，否则用0表 示，构成一个矩阵A
v3 v1 v2
v5 v6 v4
v1 v2 v3 v4 v5 v6 v1 0 v2 1 1 0 1 1 0 1 0 1 0 0
v3 1
v4 0 v5 0 v6 0
图论中的图与几何图、工程图等本质上是不同的。
图的基本概念
图论中的图是由点、点与点之间的线所组成的。通常， 我们把点与点之间不带箭头的线叫做边，带箭头的线叫 做弧。 如果一个图是由点和边所构成的，那么称为无向图， 记作G=(V，E)，其中V表示图G 的点集合，E表示图G的 边集合。连接点vi , vjV 的边记作[vi , vj]，或者[vj , vi]。 如果一个图是由点和弧所构成的，那么称为它为有向 图，记作D=(V, A)，其中V表示有向图D的点集合，A表 示有向图D的弧集合。一条方向从vi 指向vj 的弧，记作(vi , vj)。
图5.4是一个无向图G=（V，E），
其中V={v1 , v2 , v3 , v4}
E={[v1 , v2],[v2 ,v1],[v2 ,v3],
v1
v2
[v3 ,v4],[v1 ,v4],
[v2 ,v4], [v3 ,v3]}
v4 图 5.4
v3
图5.5 是一个有向图D=（V，A）
其中V={v1 ,v2 ,v3 ,v4 ,v5 ,v6 ,v7} A={(v1,v2),(v1,v3),(v3 ,v2)(v3 ,v4),(v2 ,v4),(v4 ,v5), (v4 ,v6),(v5 ,v3),(v5 ,v4), (v5 ,v6),(v6 ,v7)}
v2 （3） v5
v3
（3） （2）
v5
（4）
v1
（2）
v4（4）
v1
简单图
v4（6） 多重图
以点v为端点的边的个数称为点v的度（次），记
作 d(v), 如 图 5.4 中 d(v1)=3 ， d(v2 )=4 ， d(v3 )=4 ，
d(v4 )=3。 度为零的点称为弧立点，度为1的点称为悬挂点。 悬挂点的边称为悬挂边。度为奇数的点称为奇点， 度为偶数的点称为偶点。
简单圈：如果在一个圈中所含的边均不相同
初等圈：除起点和终点外链中所含的点均不相 同的圈；
初等链: (v1 , v2 , v3 , v6 , v7 , v5 ) 初等圈： (v1 , v2 , v3 , v5 , v4 , v1 ) 简单链：(v1 , v2 , v3 , v4 ,v5 , v3 )
5.4中的边[v3 ,v3]是环。
图的基本概念
如果两个端点之间有两条以上的边，那么
称 为 它 们 为 多 重 边 ， 如 图 5.4 中 的 边
[v1 ,v2] ,[v2 ,v1]。
v1
v2
v4
v3
一个无环，无多重边的图称为简单图，
一个无环，有多重边的图称为多重图。
v2
（3）
v3（3）
（2）
关于图的第一篇论文是瑞士数学家欧拉（E. Euler） 在1736年发表的解决“哥尼斯堡” 七桥难题的论文。 德国的哥尼斯堡城有一条普雷格尔河，河中有 两个岛屿，河的两岸和岛屿之间有七座桥相互连接， 当地的居民热衷于这样一个问题：一个散步者如何 能够走过这七座桥，并且每座桥只能走过一次，最 终回到原出发地。尽管试验者很多，但是都没有成 功。为了寻找答案，1736年欧拉将这个问题抽象成 图所示图形的一笔画问题。
v2 v1 v3
v5
v1 v2
0 0 0 0 0 0 0 0 0
v9 v v8
v3
4
v5 v6 v7 v8 v9
v4
v6
v7

矩阵A的元素全为0的行所对应的点称为汇 点 上图v8 矩阵A的元素全为0的列所对应的点称为源 点 上图v1、v9

5.2
一、树及其性质
树和最小支撑树
在各种各样的图中，有一类图是十分简单又非 常具有应用价值的图，这就是树。 例5.3 已知有六个城市，它们之间要架设电话线， 要求任意两个城市均可以互相通话，并且电话线的 总长度最短。
第五章 图与网络分析 图论
主要内容：
1 图的基本概念与基本定理