东南大学远程教育离 散 数 学第 五十五 讲主讲教师：仲新宇第四篇 图论图论是近年来发展迅速而又应用广泛的一门新兴学科。它最早起源于一些数学游戏的难题研究，
如 1736年欧拉（ L.Euler)所解决的哥尼斯堡七桥问题。 以及在民间广为流传的一些游戏问题：
例如 迷宫问题、棋盘上马的行走路线问题等等。这些古老的问题当时吸引了许多学者的注意，从而在这些问题研究的基础上，又提出了著名的四色猜想和环游世界各国的问题。
第四篇 图论图论不断发展，它在解决运筹学，网络理论，信息论，控制论，博奕论以及计算机科学等各个领域的问题时，显示出越来越大的效果。
对于这样一门应用广泛的学科，其包含的内容是丰富的，本篇我们只准备介绍基本的概念和定理，为今后有关学科及课程的学习和研究提供方便。
第四篇 图论第七章 图论
§ 1图的基本概念
§ 2路与回路
§ 3图的矩阵表示
§ 4欧拉图和汉密尔顿图
§ 5平面图
§ 6树与生成树
§ 1图的基本概念
1.基本名词和定义
,定义,一个图 G是一个三元组 <V(G),E(G),Φ G>,其中
V(G)为有限非空结点（或叫顶点）集合,E(G)是边的集合,Φ G是从边集 E到结点偶对集合上的函数。
讨论定义：
(1),V(G) ={V1,V2,…,Vn}为有限非空集合,
Vi称为结点,简称 V是点集。
(2),E(G)={e1,…,em}为有限的边集合,ei称为边，
每个 ei都有 V中的结点对与之相对应,称 E为边集 。
即每条边是连结 V中的某两个点的。
§ 1图的基本概念
(3).若Ｇ中每一条边 e与有序偶对 <vi,vj>或无序偶对 (vi,vj)相关系，则可说边 e连接结点 vi和 vj
(4).可用 e＝ <vi,vj>或 e＝ (vi,vj)，以结点来表示图的边，这样可把图简化成：Ｇ＝ <Ｖ，Ｅ >。
例：有图如下，试写成定义表达式
Ｇ＝ 〈 Ｖ，Ｅ 〉,
其中Ｖ＝ {v1,v2,v3,v4,v5}
Ｅ＝ {x1,x2,x3,x4,x5,x6}
§ 1图的基本概念例：对有向图可表示为：
Ｇ＝ 〈 Ｖ、Ｅ 〉,
其中Ｖ＝｛ a,b,c,d｝
Ｅ＝
｛ <a,b>,<b,a>,<b,d>,<d,a>,<d,d>,<c,c
>｝
下面定义一些专门名词：
(1)有向边,在图中对应有序偶对的边（或者：在图中带有箭头方向的边或弧线）
§ 1图的基本概念
(2)无向边,在图中对应无序偶对的边（或：在图中不带箭头的边）
(3)邻接结点,由一条边（有向或无向） 连接起来的结点偶对
(4)（ｎ，ｅ）图,具有ｎ个结点（顶点），ｅ条边的图
(5)有向图,在Ｇ中每一条边均为有向边
(5)有向完全图,在 n个结点的有向图 G=<V,E>中，如果
E＝ V× V，则称 G为有向完全图。
例：
东南大学远程教育离 散 数 学第 五十六 讲主讲教师：仲新宇
§ 1图的基本概念对 有向简单完全图 讲,ｅ＝ ＝ n(n-1)
（没有自回路）
22 nC?
§ 1图的基本概念
(6)无向图,每一条边均为无向边的图
(7)无向完全图,每两个结点之间均有连线的无向图。
n个结点的无向完全图的边数为：
例：
2
)1(2 nnCe
n
§ 1图的基本概念
(8)混合图,既有有向边，又有无向边的图
(9)互相邻接的边,连接于同一结点的二条（或若干条）
边例：
§ 1图的基本概念
(10)闭路（自回路）,图中起始且终止于同一结点的边
(闭路的箭头方向是没有意义的 )例：
(11)多重边（平行边）,二个结点之间方向相同的二条（多条）边例：
§ 1图的基本概念
,定义,,含有多重边的图称为 多重图,非多重图称为 线图 。
简单图,无自回路的线图称为 简单图。 由定义可见，简单图是没有自回路和多重边的图。
例：
§ 1图的基本概念
,定义,,有权图 （赋权图）Ｇ是一个三元 组 〈 Ｖ、Ｅ、
ｇ 〉 或四元组 〈 Ｖ、Ｅ、ｆ、ｇ 〉,其中Ｖ为结点集合，Ｅ为边的集合,f是定义在Ｖ上的函数,g是定义在边集合Ｅ上的函数。
实际上，有权图可以用一句话概括：每一条边或结点均注上数字的图（数字可以为整数、正实数）
例：给出一个有权图
Ｇ＝ 〈 Ｖ、Ｅ、ｆ、ｇ 〉,其图如下：
其中Ｖ＝ {v1,v2,v3}
Ｅ＝ {e1,e2}
§ 1图的基本概念
(12)孤立结点,不与任何结点相连接的结点
(13)零图,仅包含孤立结点的图，又称（ｎ，０）图
(14)平凡图,只有一个结点的图（ 1,0）图
,定义,,在有向图中，对于任何结点 v，以 v为始点的边的条数，称为结点 v的 引出度数,记作 ；以 v点为终点的边的条数称为 v的 引入度数,记作 结点的 v的引入度数和引出度数之和称为 v的度数,用 deg（ v） 表示。
由定义可见：
度 数 deg（ v）＝
对 无向图讲,结点的度数等于和该结点关联的边的条数 )(deg v?
)(deg v?
)(deg v?
)(deg v
§ 1图的基本概念例：
(15)正则图,所有结点均具有同样度数的简单无向图例：
§ 1图的基本概念
,定理,,每个图中，结点度数的总和等于边数的两倍。
n
i
i ev
1
2)d e g (
§ 1图的基本概念例：若图Ｇ有 n个顶点，（ n+1）条边，则Ｇ中至少有一个结点的度数 ≥３。
证明：设Ｇ中有 n个结点分别为 v1,v2,…,v n，则由握手定理：
而结点的平均度数 =
∴ 结点中至少有一个顶点的度数 ≥３
)1(22)d e g (
1
nevn
i
i
212)1(2 nnn
§ 1图的基本概念
,推论,,
(1)在图中，所有度数之和必为偶数；
(2)在图中，度数为奇数的结点必定有偶数个。
§ 1图的基本概念
,定理,,在任何有向图中，所有结点的入度之和等于所有结点的出度之和。
§ 1图的基本概念
２．子图和图的同构,
,定义,,设Ｇ＝ <Ｖ，Ｅ >，Ｇ’＝ <Ｖ’，Ｅ’ >
是二个图若Ｖ’?Ｖ，Ｅ’?Ｅ,则称Ｇ’是Ｇ的子图；
若Ｖ’?Ｖ或Ｅ’?Ｅ,则称Ｇ’是Ｇ的真子图；
若Ｖ’＝Ｖ，Ｅ’?Ｅ,则称Ｇ’是Ｇ的生成子图 (支撑子图 )。
例：Ｇ图如下：Ｇ的真子图,支撑子图：
§ 1图的基本概念说明：
（ 1）Ｇ也是Ｇ的生成子图；
（ 2）Ｇ’＝ 〈 Ｖ,?〉 也是Ｇ的生成子图。
它们统称为 平凡子图 。
,定义,,设Ｇ＝ 〈 Ｖ，Ｅ 〉,Ｇ’＝ 〈 Ｖ’，
Ｅ’ 〉 是Ｇ的子图，若有另一个图Ｇ’’＝
〈 Ｖ’’，Ｅ’’ 〉,且满足关系Ｅ’’＝Ｅ
－Ｅ’，Ｖ’’ 为 E’’中边的相关结点的集合，
即（Ｖ’’? Ｖ），则称：Ｇ’’为Ｇ’关于
Ｇ的补图（相对补图）。
例：
§ 1图的基本概念
Ｇ Ｇ’ Ｇ’关于Ｇ的补图
Ｇ’’
,定义,,给定一个图Ｇ，由Ｇ中的所有结点和使Ｇ成为完全图的边所组成的图，称为Ｇ的补图（绝对补图），
记为,
G
§ 1图的基本概念
Ｇ
,定义,,设Ｇ＝ 〈 Ｖ、Ｅ 〉 和Ｇ’＝ 〈 Ｖ’，Ｅ’ 〉
是两个图，若存在一双射函数：ｇ：Ｖ → Ｖ＇，当且仅当 e’＝ {g(vi),g(vj)}是Ｇ’中的一条边，才能使 e＝
{vi,vj}是Ｇ中的一条边，则称 Ｇ’和Ｇ同构 。
§ 1图的基本概念讨论定义：
（ 1）Ｇ’和Ｇ是互为同构的；
（ 2）对无向图讲“一一对应”是指保持结点之间的邻接关系；
（ 3）对有向图讲“一一对应”不但是指结点之间的邻接关系，而且还应保持边的方向和边的重数。
例 1：
§ 1图的基本概念例２：下面给出二个无向图，试求出同构函数
ｇ：｛ 1,2,3,4,5,6｝ →
},,,,,{ 654321 aaaaaa
§ 1图的基本概念两图同构的必要条件：
1.结点数相等。
2,边数相等
3.度数相同的结点数相等不是充分条件。
东南大学远程教育离 散 数 学第 五十七讲主讲教师：仲新宇
§ 1图的基本概念
２．子图和图的同构,
,定义,,设Ｇ＝ <Ｖ，Ｅ >，Ｇ’＝ <Ｖ’，Ｅ’ >
是二个图若Ｖ’?Ｖ，Ｅ’?Ｅ,则称Ｇ’是Ｇ的子图；
若Ｖ’?Ｖ或Ｅ’?Ｅ,则称Ｇ’是Ｇ的真子图；
若Ｖ’＝Ｖ，Ｅ’?Ｅ,则称Ｇ’是Ｇ的生成子图 (支撑子图 )。
例：Ｇ图如下：Ｇ的真子图,支撑子图：
§ 1图的基本概念说明：
（ 1）Ｇ也是Ｇ的生成子图；
（ 2）Ｇ’＝ 〈 Ｖ,?〉 也是Ｇ的生成子图。
它们统称为 平凡子图 。
,定义,,设Ｇ＝ 〈 Ｖ，Ｅ 〉,Ｇ’＝ 〈 Ｖ’，
Ｅ’ 〉 是Ｇ的子图，若有另一个图Ｇ’’＝
〈 Ｖ’’，Ｅ’’ 〉,且满足关系Ｅ’’＝Ｅ
－Ｅ’，Ｖ’’ 为 E’’中边的相关结点的集合，
即（Ｖ’’? Ｖ），则称：Ｇ’’为Ｇ’关于
Ｇ的补图（相对补图）。
例：
§ 1图的基本概念
Ｇ Ｇ’ Ｇ’关于Ｇ的补图
Ｇ’’
,定义,,给定一个图Ｇ，由Ｇ中的所有结点和使Ｇ成为完全图的边所组成的图，称为Ｇ的补图（绝对补图），
记为,
G
§ 1图的基本概念
Ｇ
,定义,,设Ｇ＝ 〈 Ｖ、Ｅ 〉 和Ｇ’＝ 〈 Ｖ’，Ｅ’ 〉
是两个图，若存在一双射函数：ｇ：Ｖ → Ｖ＇，当且仅当 e’＝ {g(vi),g(vj)}是Ｇ’中的一条边，才能使 e＝
{vi,vj}是Ｇ中的一条边，则称 Ｇ’和Ｇ同构 。
§ 1图的基本概念讨论定义：
（ 1）Ｇ’和Ｇ是互为同构的；
（ 2）对无向图讲“一一对应”是指保持结点之间的邻接关系；
（ 3）对有向图讲“一一对应”不但是指结点之间的邻接关系，而且还应保持边的方向和边的重数。
例 1：
§ 1图的基本概念例２：下面给出二个无向图，试求出同构函数
ｇ：｛ 1,2,3,4,5,6｝ →
},,,,,{ 654321 aaaaaa
§ 1图的基本概念两图同构的必要条件：
1.结点数相等。
2,边数相等
3.度数相同的结点数相等不是充分条件。
§ 2路与回路
1.路径和循环
,定义,,在一个图中，从某一结点出发经过某些结点到达终点的边的序列称为图的 路径,
而路径中边的条数称为 路径的长度 （路长）。
讨论定义：
（ 1）从一个结点到某一结点的路径，（若有的话）不一定是唯一的；
（ 2）路径的表示方法：
(a)边的序列表示法：
设Ｇ＝＜Ｖ，Ｅ＞为一有向图，,则路径可以表示成,(<v1,v2>,<v2,v3>,….<v k-1,vk>)
Vvi?
§ 2路与回路
(b)结点表示法：
（ 3）路径长度：若二个结点之间有一条路经Ｐ，则路径 |Ｐ |＝Ｐ中边的条数。
例：给出有向图Ｇ，求起始于１，终止于３的路径
),( 21 kvvv?
§ 2路与回路下面介绍一些专有名词：
(1)穿程全部结点的路径,经过图中所有结点的路径。
(2)简单路径,在有向图中经过边一次且仅一次的路径。
(3)基本路径,在有向图中，穿程结点均不相同的路径。
(4)循环,起始且终结于同一结点的路径。
(5)简单循环,每一条边出现一次且仅一次的循环。
(6)基本循环,通过每个结点一次且仅一次的循环。
例：在上例中，列出下列循环，判断为何种循环
§ 2路与回路
(7)非循环图,没有任何循环的简单有向图。
讨论,① 一定不包含自循环
② 不是基本路径的任何路径都会包含循环，而去掉这些循环就可以得到基本路径
2.可达性：
,定义,,设图Ｇ为简单有向图，且,若从 vi到 vj
存在任何一条路径的话，则称 vi到 vj是可达的。
可达性一定满足：
自反性：
可传递性：
Vvv ji?,
东南大学远程教育离 散 数 学第 五十八讲主讲教师：仲新宇
§ 1图的基本概念讨论定义：
（ 1）Ｇ’和Ｇ是互为同构的；
（ 2）对无向图讲“一一对应”是指保持结点之间的邻接关系；
（ 3）对有向图讲“一一对应”不但是指结点之间的邻接关系，而且还应保持边的方向和边的重数。
例 1：
§ 2路与回路
,定义,,从 vi到 vj的最短路径的长度称为距离，
并记作：
讨论定义：
(1) d<vi,vi>=0
(2) d<vi,vj>≥ 0
(3) d<vi,vj>+d<vj,vk>≥ d<vi,vk>
ji vvd,
§ 2路与回路
(4)规定：若 vi到 vj是不可达的，则
(5)若 vi到 vj是可达的，且 vj 到 vi也是可达的，则
d<vi,vi>不一定等于 d<vi,vi>
例：
ji vvd,
§ 2路与回路
3.连通性
,定义,,对于无向图中的任何结点偶对来讲，
若任何二个结点是相互可达的，则称此图是连通的。
对于有向图来讲
,定义,,对于简单有向图的伴随无向图（或称底图），若是连通的，则称此图为弱连通的；
若图中任何结点偶对中至少有一点到另一结点是可达的，则称此图是单侧连通的；如果两结点均是互相可达的，则称是强连通的。
注：伴随无向图即为去掉箭头方向的图
§ 2路与回路例：判定下列图是何种连通图：
§ 2路与回路
,定理,,一个有向图是强连通的充要条件是：
它包含一个循环，该循环至少包含每个结点一次。
证明：
§ 2路与回路
,定义,,设Ｇ＝＜Ｖ，Ｅ＞为一简单有向图，
且Ｇ’是Ｇ的子图。对于某一性质而言，若没有其他包含Ｇ’的子图具有这种性质，则称子图Ｇ’是相对于该性质的极大子图。
具有强连通性质的极大子图Ｇ’称为强分图；
具有单侧连通性质的极大子图Ｇ’称为单侧分图；
具有弱连通性质的极大子图Ｇ’称为弱分图。
§ 2路与回路例：
§ 2路与回路
,定理,,在任一简单有向图Ｇ＝＜Ｖ，Ｅ＞中，
有向图的每一个结点恰好处于一个强分图之中。
证明：
§ 3图的矩阵表示矩阵是研究图的有关性质的最有效的工具，
可运用图的矩阵运算求出图的路径、循环和其它一些性质。
１,图的邻接矩阵表示方法
,定义,,设Ｇ＝＜Ｖ，Ｅ＞是简单有向图，其中
V={v1,v2,…v n}定义一个 nxn的矩阵 A，并把其中各元素 aij表示成：
Evv
Evv
a
ji
ji
ij 〉若〈
〉若〈
,0
,1 则称矩阵 A为图 G的邻接矩阵。
§ 3图的矩阵表示例：设图Ｇ＝＜Ｖ，Ｅ＞如下图所示讨论定义：
（ 1）图 G的邻接矩阵中的元素为 0和 1,∴ 又称为布尔矩阵；
（ 2）图 G的邻接矩阵中的元素的次序是无关紧要的，只要进行行和行、列和列的交换，则可得到相同的矩阵。
§ 3图的矩阵表示
∴ 若有二个简单有向图，则可得到二个对应的邻接矩阵，若对某一矩阵进行行和行、列和列之间的交换后得到和另一矩阵相同的矩阵，则此二图同构。
（ 3）当有向图中的有向边表示关系时，邻接矩阵就是关系矩阵；
（ 4）零图的邻接矩阵称为零矩阵，即矩阵中的所有元素均为 0；
（ 5）在图的邻接矩阵中，
①行中 1的个数就是行中相应结点的引出次数
②列中 1的个数就是列中相应结点的引入次数东南大学远程教育离 散 数 学第 五十九讲主讲教师：仲新宇
§ 3图的矩阵表示
２,矩阵的计算,
１０００
１１０１
００１１
０１００
A
０１１０
０１００
１０１０
００１１
T
A
§ 3图的矩阵表示主对角线上的数表示结点 i（或 j）的引出次数。
００１１
１１３１
０２１０
１０１０
TAA
１１１２
００１１
１２０１
２１０１
AA T
主对角线上的数表示结点 i（或 j）的引入次数。
§ 3图的矩阵表示
０１００
１１１１
２１０１
００１１
AAA 2
００１１
２２１２
１２１１
２１０１
AAA 23
２１０１
３３２３
２２２３
１２１１
AAA 34
2A
3A
4A
表示 i和 j之间具有长度为 2
的路径数，
表示 i和 j之间具有长度为 3
的路径数，
表示 i和 j之间具有长度为 4
的路径数，
§ 3图的矩阵表示
bij表示从结点 vi到 vj有长度分别为 1,2,3,4的不同路径总数。
此时,bij?0，表示从 vi到 vj是可达的。
３２１２
７７４７
５５４６
３４２３
4321
4 AAAAB
§ 3图的矩阵表示
,定义,,设Ｇ＝＜Ｖ，Ｅ＞是简单有向图，
其中 |V|=ｎ（ ），定义一个 矩阵 P，
它的元素为：
则 P称为图 G的可达性矩阵。
由 矩阵可计算出可达性矩阵，其方法是：
若 中（ i,j）是非,0”元素，则对应的,
否则 。
In nn?
不存在任何路径到若至少存在一条路径到若
ji
ji
ij vv
vv
p
0
1
nB
nB
1?ijP
0?ijP
§ 3图的矩阵表示
,定义,,设无向图Ｇ＝＜Ｖ，Ｅ＞，
其中,则称 B为无向图
G的完全关联矩阵 。
3212
7747
5546
3423
432
4 AAAAB
１１１１
１１１１
１１１１
１１１１
P
},,{},,{ 2121 mn eeeEvvvV mnijbB )(令
ji
ji
ij ev
ev
b 不关联若关联若
0
1
§ 3图的矩阵表示例：
讨论定义：
（ 1）完全关联矩阵为布尔矩阵；
（ 2）对应 B中行均为 0的结点为孤立结点，
只有一个,1”的行的结点一定为悬挂的边，且一定不在任一循环中全部为 1的行的结点必定联结图中所有的结点。
§ 4欧拉图和汉密尔顿图欧拉路径：穿程图 G的每一条边一次且仅一次的路径。
欧拉循环：穿程图 G的每一条边一次且仅一次的循环。
欧拉图：具有欧拉循环的图。
,定理,,无向图 G具有一条欧拉路径，当且仅当 G是连通的，且有零个或两个奇数度数的结点。
,推论,,无向图 G具有一条欧拉循环，当且仅当 G是连通的，且所有结点度数全为偶数。
§ 4欧拉图和汉密尔顿图例：用定理解决哥尼斯堡桥的问题
§ 4欧拉图和汉密尔顿图
,定理,,设 G是一连通有向图，则当且仅当 G中每一个结点的 ＝,G
才有欧拉循环；
当且仅当除了二个结点（其中一个的引入次数比引出次数大１，另一个的引入次数比引出次数小１）以外的所有结点的
＝,则图 G才有欧拉路径。
)(deg v? )(deg v?
)(deg v? )(deg v?
§ 4欧拉图和汉密尔顿图汉密尔顿路径：穿程无向图的每一个结点一次且仅一次的路径。
汉密尔顿循环：穿程无向图的每一个结点一次且仅一次的循环。
汉密尔顿图：具有汉密尔顿循环的图。
到目前为止，还没有找到哈密尔顿路径存在的充分必要条件。下面介绍两个定理。
§ 4欧拉图和汉密尔顿图
,定理,,设Ｇ＝＜Ｖ，Ｅ＞是具有 n 个结点的简单无向图，若在 G中每对结点次数之和大于或等于
(n-1)，则在 G中一定存在一条汉密尔顿路径。
实际上，此定理只是充分条件，而不是充分必要条件。
例：ｎ＝７，Ｇ＝＜Ｖ，Ｅ＞见图：
每对结点次数为４ <７－１＝６，
但确有一条汉密尔顿路径。
§ 4欧拉图和汉密尔顿图
,定理,,若图 G=<V,E>具有汉密尔顿循环，则对于结点集 V的每个非空子集 S均有 W(G－
S)≤|S| 成立。
讨论：
(1)W(G－ S)为从 G中删除 S后，所得图的连通分支数。
(2)该定理给出的条件是 哈密尔顿图的必要条件。
例：
东南大学远程教育离 散 数 学第 六十 讲主讲教师：仲新宇
§ 5平面图先看一个例子：
有六个结点的图如右，
试问：能否转变成与其等价的，
但没有任何交线的平面上的图？
,定义,,设 G=<V,E>是一个无向图，如果能够把 G的所有结点和边画在平面上，且使得任何两条边除了端点外没有其它的交点，就称 G是一个平面图。
§ 5平面图讨论定义：
（ 1）平面上的图，一开始就画成如定义所讲的图；
例：
（ 2）原来在平面上的图形似交叉，但经过若干次的改画后，变成符合定义所规定的图；
§ 5平面图
（ 3）并非所有的图经过处理之后都可变为平面图。
如何判断一个图是否为平面图，介绍以下几种方法：
1.观察法,
找出基本循环，将交叉的边分别放置在基本循环内或外而避免交叉。
§ 5平面图
2,欧拉定理：
,定义,,平面图中四周为边所包围之最小平面块称为平面图的区域亦称面。包围区域的诸边称为此区域的边界。区域面积为有限者称为有限区域，
区域面积为无限者称为无限区域。
例：
§ 5平面图
,定理,,(欧拉公式 )设图 G是一个 (n,m)连通平面图，
它的区域数为 r，则有 n－ m＋ r＝ 2。
,推论,,设图 G是一个 (n,m)连通简单平面图，若
n≥ 3则 m≤3n-6。
定理和推论给出了是平面图的必要条件，若不满足这些条件，则一定不是平面图。
例：
§ 5平面图
3．库拉托夫斯基（ Kuratowski 波兰数学家）定理：
给定两个图：
我们做以下的工作：
(1)在左边图的中间联线上插入一个度数为 2的结点，
则把一条边分成了二条边；
(2)在右边图中去掉一个度数为 2的结点，
则把二条边变成一条边。
此二项工作不会影响图的平面性。
2度结点内同构 。
§ 5平面图
,定义,,设 G1,G2是二个图，如果它们是同构的，或可以通过反复插入或删除度数为 2的结点，使得 G1和 G2同构，则称 G1,G2为 2度结点内同构。
例：下列二对图是度数为 2的结点同构
§ 5平面图
,定理,,（ Kuratowski定理）
设 G是一个图，当且仅当 G不包含任何在度数为 2
的结点内与 K3,3和 K5图同构的子图时，则 G才是平面图。
这一定理给出了一个图是平面图的充要条件。
§ 6树与生成树
1.无向树（树）
,定义,,连通的且无循环的无向图称为无向树。
例：
专用名词：
树叶 (终点 )：树中度数为 1的结点。
内点 (分枝点 )：树中度数大于 1的结点。
森林：每个连通分图均为树的图。
§ 6树与生成树树的性质：
,定理 1,：设 T是一棵树,vi,vj为 T中两个不同的结点，则,1) vi和 vj仅有一条路径相连通。
2)在 T中加一条边 {vi,vj}，则由此而形成的图，仅有一个循环。
例：
东南大学远程教育离 散 数 学第 六十 一讲主讲教师：仲新宇
§ 6树与生成树
,定理 2,：在一棵 (n,e)树中有 e=n-1。 (n表示结点数，
e表示边数 )
证明：
§ 6树与生成树
,推论,,设 F是由 t棵树组成的 (n,e)森林，则有
e=n-t。
,定理 3,：在结点大于 2的 (n,e)树中，所有结点的度数之和为 2(n-1)。
,定理 4,：在任一 (n≥2) 的树 T中，至少有二片树叶。
§ 6树与生成树
2.生成树
,定义,,一个无向图 G的生成子图是树 TG，则称 TG是 G的生成树 (支撑树 )。
讨论定义：
1)G的生成树不是唯一的。
例：
§ 6树与生成树
2)如何在连通图 G中寻找一棵生成树：
①若 G没有循环，则 G本身就是一棵树；
②若 G仅有一条循环，从此循环中删去一条边，
仍保持图的连通性，得到一棵生成树。
③若 G有多条循环，则逐个对每条循环重复 ②
中操作，直到打断 G中所有循环，得到一棵生成树为止。
,定理,,任何连通图至少有一棵生成树。
§ 6树与生成树给定一个连通图，寻找其生成树的数目是图论中树的计数问题。
,定理,,含 n(n>1)个结点的标记完全图 Kn有 nn-2
棵标记生成树。
例：
§ 6树与生成树
,定义,,生成树 T中的边称为树枝，不在生成树 T中但属于图 G的边，称为树 T的弦，弦的集合称为树 T的补。
例：
,定义,,在一个连通赋权图中，树枝的权之和为最小的生成树称为最小生成树。
Kruskal算法：
设 G有 n个结点,m条边，先将 G中所有边按权的大小次序进行排列，不妨设：
W(e1)<W(e2)<…<W(e m)，
① k?1,A。
§ 6树与生成树
② 若 A?{ek}导出的子图中不包含简单循环，则
A? A?{ek}
③ 若 A中已有 n-1条边，则算法终止，否则 K
K+1，转至 ②。
例：
§ 6树与生成树这一算法假设 G中权均不相同，对于边权任意情况也完全适用。这时求得的最小生成树不唯一。
例：
东南大学远程教育离 散 数 学第 六十二 讲主讲教师：仲新宇
§ 7有向树与根树
,定义,,若有向图在不考虑边的方向时是一棵树，称之为有向树。
,定义,,一棵有向树，如果恰有一个结点的入度为 0，其余所有结点的入度都为 1，则称为根树。入度为 0的结点称为根，出度为 0的结点称为叶，出度不为 0的结点称为分枝点或内点。
任何结点的级 (高度 )是从根出发到该结点的路径长度 (边的条数 )。
例：
§ 7有向树与根树
,定义,,指明了根树中结点或边的次序的树称为有序树。在有序树中，如每个结点有明确的级，同一级的结点排在同一行，并明确它们的位置，则这样的树称位置树。
例：
§ 7有向树与根树
,定义,,在根树中，若每一个结点的出度小于或等于 m，则称这棵树为 m叉树。若每个结点的出度恰好等于 m或零，则称这棵树为完全 m
叉树，若其所有树叶层次相同，称为正则 m叉树。
特别，当 m=2时，称为二叉树。
很多实际问题可用二叉树或 m叉树表示。 任何一棵有序树都可以把它改写为一棵对应的二叉树。
,定义,,在有向树 T中，由结点 V和它的所有子孙所构成的结点子集 V’以及从 V出发的所有有向路中的边所构成的边集 E’组成 T的子图
T’=<V’,E’>，称为是以 V为根的子树。
§ 7有向树与根树方法：
设有序树 T中结点 Vi的 r棵子树有根 Vi1,Vi2,…V ir,其顺序自左向右，则在二叉树 T’中 Vi1是 Vi的左儿子,Vi2是 Vi1的右儿子,Vi3是 Vi2的右儿子 ….,
Vir是 Vir－ 1的右儿子。
例：
本篇小结通过本篇的学习应达到以下基本要求：
(1)牢记图论基本定理 (握手定理 )，并能灵活地应有它。
(2)记住简单图的概念，弄清楚那些概念是用简单图定义的。
(3)明白图之间同构的概念，会根据定义判断阶数
n较小的两个图是否同构。
(4)弄清图中路径和循环的概念及其分类。
(5)在讨论图的连通性时，要特别注意有向连通图的分类及它们之间的关系。
(6)在图的矩阵表示中，可以用有向图的邻接矩阵及各次幂，求图中的路径数。
本篇小结
(7)明确只存在欧拉路径而无欧拉循环的图不是欧拉图，同样，只存在汉密尔顿路径不含汉密尔顿循环的图不是汉密尔顿图。
(8)注意对于汉密尔顿图，我们只给出了汉密尔顿图存在的充分条件和必要条件。仍没有找到充分必要条件。
(9)掌握平面图的概念及判定平面图的几种方法。
(10)掌握树的定义和性质并利用握手定理求树中结点的度数，会求连通图的生成树，用 Kruskal
算法求最小生成树。
(11)掌握根树、有序树,m叉树的概念，任何一棵有序树都可以改写成为二叉树。
如 1736年欧拉（ L.Euler)所解决的哥尼斯堡七桥问题。 以及在民间广为流传的一些游戏问题：
例如 迷宫问题、棋盘上马的行走路线问题等等。这些古老的问题当时吸引了许多学者的注意，从而在这些问题研究的基础上，又提出了著名的四色猜想和环游世界各国的问题。
第四篇 图论图论不断发展，它在解决运筹学，网络理论，信息论，控制论，博奕论以及计算机科学等各个领域的问题时，显示出越来越大的效果。
对于这样一门应用广泛的学科，其包含的内容是丰富的，本篇我们只准备介绍基本的概念和定理，为今后有关学科及课程的学习和研究提供方便。
第四篇 图论第七章 图论
§ 1图的基本概念
§ 2路与回路
§ 3图的矩阵表示
§ 4欧拉图和汉密尔顿图
§ 5平面图
§ 6树与生成树
§ 1图的基本概念
1.基本名词和定义
,定义,一个图 G是一个三元组 <V(G),E(G),Φ G>,其中
V(G)为有限非空结点（或叫顶点）集合,E(G)是边的集合,Φ G是从边集 E到结点偶对集合上的函数。
讨论定义：
(1),V(G) ={V1,V2,…,Vn}为有限非空集合,
Vi称为结点,简称 V是点集。
(2),E(G)={e1,…,em}为有限的边集合,ei称为边，
每个 ei都有 V中的结点对与之相对应,称 E为边集 。
即每条边是连结 V中的某两个点的。
§ 1图的基本概念
(3).若Ｇ中每一条边 e与有序偶对 <vi,vj>或无序偶对 (vi,vj)相关系，则可说边 e连接结点 vi和 vj
(4).可用 e＝ <vi,vj>或 e＝ (vi,vj)，以结点来表示图的边，这样可把图简化成：Ｇ＝ <Ｖ，Ｅ >。
例：有图如下，试写成定义表达式
Ｇ＝ 〈 Ｖ，Ｅ 〉,
其中Ｖ＝ {v1,v2,v3,v4,v5}
Ｅ＝ {x1,x2,x3,x4,x5,x6}
§ 1图的基本概念例：对有向图可表示为：
Ｇ＝ 〈 Ｖ、Ｅ 〉,
其中Ｖ＝｛ a,b,c,d｝
Ｅ＝
｛ <a,b>,<b,a>,<b,d>,<d,a>,<d,d>,<c,c
>｝
下面定义一些专门名词：
(1)有向边,在图中对应有序偶对的边（或者：在图中带有箭头方向的边或弧线）
§ 1图的基本概念
(2)无向边,在图中对应无序偶对的边（或：在图中不带箭头的边）
(3)邻接结点,由一条边（有向或无向） 连接起来的结点偶对
(4)（ｎ，ｅ）图,具有ｎ个结点（顶点），ｅ条边的图
(5)有向图,在Ｇ中每一条边均为有向边
(5)有向完全图,在 n个结点的有向图 G=<V,E>中，如果
E＝ V× V，则称 G为有向完全图。
例：
东南大学远程教育离 散 数 学第 五十六 讲主讲教师：仲新宇
§ 1图的基本概念对 有向简单完全图 讲,ｅ＝ ＝ n(n-1)
（没有自回路）
22 nC?
§ 1图的基本概念
(6)无向图,每一条边均为无向边的图
(7)无向完全图,每两个结点之间均有连线的无向图。
n个结点的无向完全图的边数为：
例：
2
)1(2 nnCe
n
§ 1图的基本概念
(8)混合图,既有有向边，又有无向边的图
(9)互相邻接的边,连接于同一结点的二条（或若干条）
边例：
§ 1图的基本概念
(10)闭路（自回路）,图中起始且终止于同一结点的边
(闭路的箭头方向是没有意义的 )例：
(11)多重边（平行边）,二个结点之间方向相同的二条（多条）边例：
§ 1图的基本概念
,定义,,含有多重边的图称为 多重图,非多重图称为 线图 。
简单图,无自回路的线图称为 简单图。 由定义可见，简单图是没有自回路和多重边的图。
例：
§ 1图的基本概念
,定义,,有权图 （赋权图）Ｇ是一个三元 组 〈 Ｖ、Ｅ、
ｇ 〉 或四元组 〈 Ｖ、Ｅ、ｆ、ｇ 〉,其中Ｖ为结点集合，Ｅ为边的集合,f是定义在Ｖ上的函数,g是定义在边集合Ｅ上的函数。
实际上，有权图可以用一句话概括：每一条边或结点均注上数字的图（数字可以为整数、正实数）
例：给出一个有权图
Ｇ＝ 〈 Ｖ、Ｅ、ｆ、ｇ 〉,其图如下：
其中Ｖ＝ {v1,v2,v3}
Ｅ＝ {e1,e2}
§ 1图的基本概念
(12)孤立结点,不与任何结点相连接的结点
(13)零图,仅包含孤立结点的图，又称（ｎ，０）图
(14)平凡图,只有一个结点的图（ 1,0）图
,定义,,在有向图中，对于任何结点 v，以 v为始点的边的条数，称为结点 v的 引出度数,记作 ；以 v点为终点的边的条数称为 v的 引入度数,记作 结点的 v的引入度数和引出度数之和称为 v的度数,用 deg（ v） 表示。
由定义可见：
度 数 deg（ v）＝
对 无向图讲,结点的度数等于和该结点关联的边的条数 )(deg v?
)(deg v?
)(deg v?
)(deg v
§ 1图的基本概念例：
(15)正则图,所有结点均具有同样度数的简单无向图例：
§ 1图的基本概念
,定理,,每个图中，结点度数的总和等于边数的两倍。
n
i
i ev
1
2)d e g (
§ 1图的基本概念例：若图Ｇ有 n个顶点，（ n+1）条边，则Ｇ中至少有一个结点的度数 ≥３。
证明：设Ｇ中有 n个结点分别为 v1,v2,…,v n，则由握手定理：
而结点的平均度数 =
∴ 结点中至少有一个顶点的度数 ≥３
)1(22)d e g (
1
nevn
i
i
212)1(2 nnn
§ 1图的基本概念
,推论,,
(1)在图中，所有度数之和必为偶数；
(2)在图中，度数为奇数的结点必定有偶数个。
§ 1图的基本概念
,定理,,在任何有向图中，所有结点的入度之和等于所有结点的出度之和。
§ 1图的基本概念
２．子图和图的同构,
,定义,,设Ｇ＝ <Ｖ，Ｅ >，Ｇ’＝ <Ｖ’，Ｅ’ >
是二个图若Ｖ’?Ｖ，Ｅ’?Ｅ,则称Ｇ’是Ｇ的子图；
若Ｖ’?Ｖ或Ｅ’?Ｅ,则称Ｇ’是Ｇ的真子图；
若Ｖ’＝Ｖ，Ｅ’?Ｅ,则称Ｇ’是Ｇ的生成子图 (支撑子图 )。
例：Ｇ图如下：Ｇ的真子图,支撑子图：
§ 1图的基本概念说明：
（ 1）Ｇ也是Ｇ的生成子图；
（ 2）Ｇ’＝ 〈 Ｖ,?〉 也是Ｇ的生成子图。
它们统称为 平凡子图 。
,定义,,设Ｇ＝ 〈 Ｖ，Ｅ 〉,Ｇ’＝ 〈 Ｖ’，
Ｅ’ 〉 是Ｇ的子图，若有另一个图Ｇ’’＝
〈 Ｖ’’，Ｅ’’ 〉,且满足关系Ｅ’’＝Ｅ
－Ｅ’，Ｖ’’ 为 E’’中边的相关结点的集合，
即（Ｖ’’? Ｖ），则称：Ｇ’’为Ｇ’关于
Ｇ的补图（相对补图）。
例：
§ 1图的基本概念
Ｇ Ｇ’ Ｇ’关于Ｇ的补图
Ｇ’’
,定义,,给定一个图Ｇ，由Ｇ中的所有结点和使Ｇ成为完全图的边所组成的图，称为Ｇ的补图（绝对补图），
记为,
G
§ 1图的基本概念
Ｇ
,定义,,设Ｇ＝ 〈 Ｖ、Ｅ 〉 和Ｇ’＝ 〈 Ｖ’，Ｅ’ 〉
是两个图，若存在一双射函数：ｇ：Ｖ → Ｖ＇，当且仅当 e’＝ {g(vi),g(vj)}是Ｇ’中的一条边，才能使 e＝
{vi,vj}是Ｇ中的一条边，则称 Ｇ’和Ｇ同构 。
§ 1图的基本概念讨论定义：
（ 1）Ｇ’和Ｇ是互为同构的；
（ 2）对无向图讲“一一对应”是指保持结点之间的邻接关系；
（ 3）对有向图讲“一一对应”不但是指结点之间的邻接关系，而且还应保持边的方向和边的重数。
例 1：
§ 1图的基本概念例２：下面给出二个无向图，试求出同构函数
ｇ：｛ 1,2,3,4,5,6｝ →
},,,,,{ 654321 aaaaaa
§ 1图的基本概念两图同构的必要条件：
1.结点数相等。
2,边数相等
3.度数相同的结点数相等不是充分条件。
东南大学远程教育离 散 数 学第 五十七讲主讲教师：仲新宇
§ 1图的基本概念
２．子图和图的同构,
,定义,,设Ｇ＝ <Ｖ，Ｅ >，Ｇ’＝ <Ｖ’，Ｅ’ >
是二个图若Ｖ’?Ｖ，Ｅ’?Ｅ,则称Ｇ’是Ｇ的子图；
若Ｖ’?Ｖ或Ｅ’?Ｅ,则称Ｇ’是Ｇ的真子图；
若Ｖ’＝Ｖ，Ｅ’?Ｅ,则称Ｇ’是Ｇ的生成子图 (支撑子图 )。
例：Ｇ图如下：Ｇ的真子图,支撑子图：
§ 1图的基本概念说明：
（ 1）Ｇ也是Ｇ的生成子图；
（ 2）Ｇ’＝ 〈 Ｖ,?〉 也是Ｇ的生成子图。
它们统称为 平凡子图 。
,定义,,设Ｇ＝ 〈 Ｖ，Ｅ 〉,Ｇ’＝ 〈 Ｖ’，
Ｅ’ 〉 是Ｇ的子图，若有另一个图Ｇ’’＝
〈 Ｖ’’，Ｅ’’ 〉,且满足关系Ｅ’’＝Ｅ
－Ｅ’，Ｖ’’ 为 E’’中边的相关结点的集合，
即（Ｖ’’? Ｖ），则称：Ｇ’’为Ｇ’关于
Ｇ的补图（相对补图）。
例：
§ 1图的基本概念
Ｇ Ｇ’ Ｇ’关于Ｇ的补图
Ｇ’’
,定义,,给定一个图Ｇ，由Ｇ中的所有结点和使Ｇ成为完全图的边所组成的图，称为Ｇ的补图（绝对补图），
记为,
G
§ 1图的基本概念
Ｇ
,定义,,设Ｇ＝ 〈 Ｖ、Ｅ 〉 和Ｇ’＝ 〈 Ｖ’，Ｅ’ 〉
是两个图，若存在一双射函数：ｇ：Ｖ → Ｖ＇，当且仅当 e’＝ {g(vi),g(vj)}是Ｇ’中的一条边，才能使 e＝
{vi,vj}是Ｇ中的一条边，则称 Ｇ’和Ｇ同构 。
§ 1图的基本概念讨论定义：
（ 1）Ｇ’和Ｇ是互为同构的；
（ 2）对无向图讲“一一对应”是指保持结点之间的邻接关系；
（ 3）对有向图讲“一一对应”不但是指结点之间的邻接关系，而且还应保持边的方向和边的重数。
例 1：
§ 1图的基本概念例２：下面给出二个无向图，试求出同构函数
ｇ：｛ 1,2,3,4,5,6｝ →
},,,,,{ 654321 aaaaaa
§ 1图的基本概念两图同构的必要条件：
1.结点数相等。
2,边数相等
3.度数相同的结点数相等不是充分条件。
§ 2路与回路
1.路径和循环
,定义,,在一个图中，从某一结点出发经过某些结点到达终点的边的序列称为图的 路径,
而路径中边的条数称为 路径的长度 （路长）。
讨论定义：
（ 1）从一个结点到某一结点的路径，（若有的话）不一定是唯一的；
（ 2）路径的表示方法：
(a)边的序列表示法：
设Ｇ＝＜Ｖ，Ｅ＞为一有向图，,则路径可以表示成,(<v1,v2>,<v2,v3>,….<v k-1,vk>)
Vvi?
§ 2路与回路
(b)结点表示法：
（ 3）路径长度：若二个结点之间有一条路经Ｐ，则路径 |Ｐ |＝Ｐ中边的条数。
例：给出有向图Ｇ，求起始于１，终止于３的路径
),( 21 kvvv?
§ 2路与回路下面介绍一些专有名词：
(1)穿程全部结点的路径,经过图中所有结点的路径。
(2)简单路径,在有向图中经过边一次且仅一次的路径。
(3)基本路径,在有向图中，穿程结点均不相同的路径。
(4)循环,起始且终结于同一结点的路径。
(5)简单循环,每一条边出现一次且仅一次的循环。
(6)基本循环,通过每个结点一次且仅一次的循环。
例：在上例中，列出下列循环，判断为何种循环
§ 2路与回路
(7)非循环图,没有任何循环的简单有向图。
讨论,① 一定不包含自循环
② 不是基本路径的任何路径都会包含循环，而去掉这些循环就可以得到基本路径
2.可达性：
,定义,,设图Ｇ为简单有向图，且,若从 vi到 vj
存在任何一条路径的话，则称 vi到 vj是可达的。
可达性一定满足：
自反性：
可传递性：
Vvv ji?,
东南大学远程教育离 散 数 学第 五十八讲主讲教师：仲新宇
§ 1图的基本概念讨论定义：
（ 1）Ｇ’和Ｇ是互为同构的；
（ 2）对无向图讲“一一对应”是指保持结点之间的邻接关系；
（ 3）对有向图讲“一一对应”不但是指结点之间的邻接关系，而且还应保持边的方向和边的重数。
例 1：
§ 2路与回路
,定义,,从 vi到 vj的最短路径的长度称为距离，
并记作：
讨论定义：
(1) d<vi,vi>=0
(2) d<vi,vj>≥ 0
(3) d<vi,vj>+d<vj,vk>≥ d<vi,vk>
ji vvd,
§ 2路与回路
(4)规定：若 vi到 vj是不可达的，则
(5)若 vi到 vj是可达的，且 vj 到 vi也是可达的，则
d<vi,vi>不一定等于 d<vi,vi>
例：
ji vvd,
§ 2路与回路
3.连通性
,定义,,对于无向图中的任何结点偶对来讲，
若任何二个结点是相互可达的，则称此图是连通的。
对于有向图来讲
,定义,,对于简单有向图的伴随无向图（或称底图），若是连通的，则称此图为弱连通的；
若图中任何结点偶对中至少有一点到另一结点是可达的，则称此图是单侧连通的；如果两结点均是互相可达的，则称是强连通的。
注：伴随无向图即为去掉箭头方向的图
§ 2路与回路例：判定下列图是何种连通图：
§ 2路与回路
,定理,,一个有向图是强连通的充要条件是：
它包含一个循环，该循环至少包含每个结点一次。
证明：
§ 2路与回路
,定义,,设Ｇ＝＜Ｖ，Ｅ＞为一简单有向图，
且Ｇ’是Ｇ的子图。对于某一性质而言，若没有其他包含Ｇ’的子图具有这种性质，则称子图Ｇ’是相对于该性质的极大子图。
具有强连通性质的极大子图Ｇ’称为强分图；
具有单侧连通性质的极大子图Ｇ’称为单侧分图；
具有弱连通性质的极大子图Ｇ’称为弱分图。
§ 2路与回路例：
§ 2路与回路
,定理,,在任一简单有向图Ｇ＝＜Ｖ，Ｅ＞中，
有向图的每一个结点恰好处于一个强分图之中。
证明：
§ 3图的矩阵表示矩阵是研究图的有关性质的最有效的工具，
可运用图的矩阵运算求出图的路径、循环和其它一些性质。
１,图的邻接矩阵表示方法
,定义,,设Ｇ＝＜Ｖ，Ｅ＞是简单有向图，其中
V={v1,v2,…v n}定义一个 nxn的矩阵 A，并把其中各元素 aij表示成：
Evv
Evv
a
ji
ji
ij 〉若〈
〉若〈
,0
,1 则称矩阵 A为图 G的邻接矩阵。
§ 3图的矩阵表示例：设图Ｇ＝＜Ｖ，Ｅ＞如下图所示讨论定义：
（ 1）图 G的邻接矩阵中的元素为 0和 1,∴ 又称为布尔矩阵；
（ 2）图 G的邻接矩阵中的元素的次序是无关紧要的，只要进行行和行、列和列的交换，则可得到相同的矩阵。
§ 3图的矩阵表示
∴ 若有二个简单有向图，则可得到二个对应的邻接矩阵，若对某一矩阵进行行和行、列和列之间的交换后得到和另一矩阵相同的矩阵，则此二图同构。
（ 3）当有向图中的有向边表示关系时，邻接矩阵就是关系矩阵；
（ 4）零图的邻接矩阵称为零矩阵，即矩阵中的所有元素均为 0；
（ 5）在图的邻接矩阵中，
①行中 1的个数就是行中相应结点的引出次数
②列中 1的个数就是列中相应结点的引入次数东南大学远程教育离 散 数 学第 五十九讲主讲教师：仲新宇
§ 3图的矩阵表示
２,矩阵的计算,
１０００
１１０１
００１１
０１００
A
０１１０
０１００
１０１０
００１１
T
A
§ 3图的矩阵表示主对角线上的数表示结点 i（或 j）的引出次数。
００１１
１１３１
０２１０
１０１０
TAA
１１１２
００１１
１２０１
２１０１
AA T
主对角线上的数表示结点 i（或 j）的引入次数。
§ 3图的矩阵表示
０１００
１１１１
２１０１
００１１
AAA 2
００１１
２２１２
１２１１
２１０１
AAA 23
２１０１
３３２３
２２２３
１２１１
AAA 34
2A
3A
4A
表示 i和 j之间具有长度为 2
的路径数，
表示 i和 j之间具有长度为 3
的路径数，
表示 i和 j之间具有长度为 4
的路径数，
§ 3图的矩阵表示
bij表示从结点 vi到 vj有长度分别为 1,2,3,4的不同路径总数。
此时,bij?0，表示从 vi到 vj是可达的。
３２１２
７７４７
５５４６
３４２３
4321
4 AAAAB
§ 3图的矩阵表示
,定义,,设Ｇ＝＜Ｖ，Ｅ＞是简单有向图，
其中 |V|=ｎ（ ），定义一个 矩阵 P，
它的元素为：
则 P称为图 G的可达性矩阵。
由 矩阵可计算出可达性矩阵，其方法是：
若 中（ i,j）是非,0”元素，则对应的,
否则 。
In nn?
不存在任何路径到若至少存在一条路径到若
ji
ji
ij vv
vv
p
0
1
nB
nB
1?ijP
0?ijP
§ 3图的矩阵表示
,定义,,设无向图Ｇ＝＜Ｖ，Ｅ＞，
其中,则称 B为无向图
G的完全关联矩阵 。
3212
7747
5546
3423
432
4 AAAAB
１１１１
１１１１
１１１１
１１１１
P
},,{},,{ 2121 mn eeeEvvvV mnijbB )(令
ji
ji
ij ev
ev
b 不关联若关联若
0
1
§ 3图的矩阵表示例：
讨论定义：
（ 1）完全关联矩阵为布尔矩阵；
（ 2）对应 B中行均为 0的结点为孤立结点，
只有一个,1”的行的结点一定为悬挂的边，且一定不在任一循环中全部为 1的行的结点必定联结图中所有的结点。
§ 4欧拉图和汉密尔顿图欧拉路径：穿程图 G的每一条边一次且仅一次的路径。
欧拉循环：穿程图 G的每一条边一次且仅一次的循环。
欧拉图：具有欧拉循环的图。
,定理,,无向图 G具有一条欧拉路径，当且仅当 G是连通的，且有零个或两个奇数度数的结点。
,推论,,无向图 G具有一条欧拉循环，当且仅当 G是连通的，且所有结点度数全为偶数。
§ 4欧拉图和汉密尔顿图例：用定理解决哥尼斯堡桥的问题
§ 4欧拉图和汉密尔顿图
,定理,,设 G是一连通有向图，则当且仅当 G中每一个结点的 ＝,G
才有欧拉循环；
当且仅当除了二个结点（其中一个的引入次数比引出次数大１，另一个的引入次数比引出次数小１）以外的所有结点的
＝,则图 G才有欧拉路径。
)(deg v? )(deg v?
)(deg v? )(deg v?
§ 4欧拉图和汉密尔顿图汉密尔顿路径：穿程无向图的每一个结点一次且仅一次的路径。
汉密尔顿循环：穿程无向图的每一个结点一次且仅一次的循环。
汉密尔顿图：具有汉密尔顿循环的图。
到目前为止，还没有找到哈密尔顿路径存在的充分必要条件。下面介绍两个定理。
§ 4欧拉图和汉密尔顿图
,定理,,设Ｇ＝＜Ｖ，Ｅ＞是具有 n 个结点的简单无向图，若在 G中每对结点次数之和大于或等于
(n-1)，则在 G中一定存在一条汉密尔顿路径。
实际上，此定理只是充分条件，而不是充分必要条件。
例：ｎ＝７，Ｇ＝＜Ｖ，Ｅ＞见图：
每对结点次数为４ <７－１＝６，
但确有一条汉密尔顿路径。
§ 4欧拉图和汉密尔顿图
,定理,,若图 G=<V,E>具有汉密尔顿循环，则对于结点集 V的每个非空子集 S均有 W(G－
S)≤|S| 成立。
讨论：
(1)W(G－ S)为从 G中删除 S后，所得图的连通分支数。
(2)该定理给出的条件是 哈密尔顿图的必要条件。
例：
东南大学远程教育离 散 数 学第 六十 讲主讲教师：仲新宇
§ 5平面图先看一个例子：
有六个结点的图如右，
试问：能否转变成与其等价的，
但没有任何交线的平面上的图？
,定义,,设 G=<V,E>是一个无向图，如果能够把 G的所有结点和边画在平面上，且使得任何两条边除了端点外没有其它的交点，就称 G是一个平面图。
§ 5平面图讨论定义：
（ 1）平面上的图，一开始就画成如定义所讲的图；
例：
（ 2）原来在平面上的图形似交叉，但经过若干次的改画后，变成符合定义所规定的图；
§ 5平面图
（ 3）并非所有的图经过处理之后都可变为平面图。
如何判断一个图是否为平面图，介绍以下几种方法：
1.观察法,
找出基本循环，将交叉的边分别放置在基本循环内或外而避免交叉。
§ 5平面图
2,欧拉定理：
,定义,,平面图中四周为边所包围之最小平面块称为平面图的区域亦称面。包围区域的诸边称为此区域的边界。区域面积为有限者称为有限区域，
区域面积为无限者称为无限区域。
例：
§ 5平面图
,定理,,(欧拉公式 )设图 G是一个 (n,m)连通平面图，
它的区域数为 r，则有 n－ m＋ r＝ 2。
,推论,,设图 G是一个 (n,m)连通简单平面图，若
n≥ 3则 m≤3n-6。
定理和推论给出了是平面图的必要条件，若不满足这些条件，则一定不是平面图。
例：
§ 5平面图
3．库拉托夫斯基（ Kuratowski 波兰数学家）定理：
给定两个图：
我们做以下的工作：
(1)在左边图的中间联线上插入一个度数为 2的结点，
则把一条边分成了二条边；
(2)在右边图中去掉一个度数为 2的结点，
则把二条边变成一条边。
此二项工作不会影响图的平面性。
2度结点内同构 。
§ 5平面图
,定义,,设 G1,G2是二个图，如果它们是同构的，或可以通过反复插入或删除度数为 2的结点，使得 G1和 G2同构，则称 G1,G2为 2度结点内同构。
例：下列二对图是度数为 2的结点同构
§ 5平面图
,定理,,（ Kuratowski定理）
设 G是一个图，当且仅当 G不包含任何在度数为 2
的结点内与 K3,3和 K5图同构的子图时，则 G才是平面图。
这一定理给出了一个图是平面图的充要条件。
§ 6树与生成树
1.无向树（树）
,定义,,连通的且无循环的无向图称为无向树。
例：
专用名词：
树叶 (终点 )：树中度数为 1的结点。
内点 (分枝点 )：树中度数大于 1的结点。
森林：每个连通分图均为树的图。
§ 6树与生成树树的性质：
,定理 1,：设 T是一棵树,vi,vj为 T中两个不同的结点，则,1) vi和 vj仅有一条路径相连通。
2)在 T中加一条边 {vi,vj}，则由此而形成的图，仅有一个循环。
例：
东南大学远程教育离 散 数 学第 六十 一讲主讲教师：仲新宇
§ 6树与生成树
,定理 2,：在一棵 (n,e)树中有 e=n-1。 (n表示结点数，
e表示边数 )
证明：
§ 6树与生成树
,推论,,设 F是由 t棵树组成的 (n,e)森林，则有
e=n-t。
,定理 3,：在结点大于 2的 (n,e)树中，所有结点的度数之和为 2(n-1)。
,定理 4,：在任一 (n≥2) 的树 T中，至少有二片树叶。
§ 6树与生成树
2.生成树
,定义,,一个无向图 G的生成子图是树 TG，则称 TG是 G的生成树 (支撑树 )。
讨论定义：
1)G的生成树不是唯一的。
例：
§ 6树与生成树
2)如何在连通图 G中寻找一棵生成树：
①若 G没有循环，则 G本身就是一棵树；
②若 G仅有一条循环，从此循环中删去一条边，
仍保持图的连通性，得到一棵生成树。
③若 G有多条循环，则逐个对每条循环重复 ②
中操作，直到打断 G中所有循环，得到一棵生成树为止。
,定理,,任何连通图至少有一棵生成树。
§ 6树与生成树给定一个连通图，寻找其生成树的数目是图论中树的计数问题。
,定理,,含 n(n>1)个结点的标记完全图 Kn有 nn-2
棵标记生成树。
例：
§ 6树与生成树
,定义,,生成树 T中的边称为树枝，不在生成树 T中但属于图 G的边，称为树 T的弦，弦的集合称为树 T的补。
例：
,定义,,在一个连通赋权图中，树枝的权之和为最小的生成树称为最小生成树。
Kruskal算法：
设 G有 n个结点,m条边，先将 G中所有边按权的大小次序进行排列，不妨设：
W(e1)<W(e2)<…<W(e m)，
① k?1,A。
§ 6树与生成树
② 若 A?{ek}导出的子图中不包含简单循环，则
A? A?{ek}
③ 若 A中已有 n-1条边，则算法终止，否则 K
K+1，转至 ②。
例：
§ 6树与生成树这一算法假设 G中权均不相同，对于边权任意情况也完全适用。这时求得的最小生成树不唯一。
例：
东南大学远程教育离 散 数 学第 六十二 讲主讲教师：仲新宇
§ 7有向树与根树
,定义,,若有向图在不考虑边的方向时是一棵树，称之为有向树。
,定义,,一棵有向树，如果恰有一个结点的入度为 0，其余所有结点的入度都为 1，则称为根树。入度为 0的结点称为根，出度为 0的结点称为叶，出度不为 0的结点称为分枝点或内点。
任何结点的级 (高度 )是从根出发到该结点的路径长度 (边的条数 )。
例：
§ 7有向树与根树
,定义,,指明了根树中结点或边的次序的树称为有序树。在有序树中，如每个结点有明确的级，同一级的结点排在同一行，并明确它们的位置，则这样的树称位置树。
例：
§ 7有向树与根树
,定义,,在根树中，若每一个结点的出度小于或等于 m，则称这棵树为 m叉树。若每个结点的出度恰好等于 m或零，则称这棵树为完全 m
叉树，若其所有树叶层次相同，称为正则 m叉树。
特别，当 m=2时，称为二叉树。
很多实际问题可用二叉树或 m叉树表示。 任何一棵有序树都可以把它改写为一棵对应的二叉树。
,定义,,在有向树 T中，由结点 V和它的所有子孙所构成的结点子集 V’以及从 V出发的所有有向路中的边所构成的边集 E’组成 T的子图
T’=<V’,E’>，称为是以 V为根的子树。
§ 7有向树与根树方法：
设有序树 T中结点 Vi的 r棵子树有根 Vi1,Vi2,…V ir,其顺序自左向右，则在二叉树 T’中 Vi1是 Vi的左儿子,Vi2是 Vi1的右儿子,Vi3是 Vi2的右儿子 ….,
Vir是 Vir－ 1的右儿子。
例：
本篇小结通过本篇的学习应达到以下基本要求：
(1)牢记图论基本定理 (握手定理 )，并能灵活地应有它。
(2)记住简单图的概念，弄清楚那些概念是用简单图定义的。
(3)明白图之间同构的概念，会根据定义判断阶数
n较小的两个图是否同构。
(4)弄清图中路径和循环的概念及其分类。
(5)在讨论图的连通性时，要特别注意有向连通图的分类及它们之间的关系。
(6)在图的矩阵表示中，可以用有向图的邻接矩阵及各次幂，求图中的路径数。
本篇小结
(7)明确只存在欧拉路径而无欧拉循环的图不是欧拉图，同样，只存在汉密尔顿路径不含汉密尔顿循环的图不是汉密尔顿图。
(8)注意对于汉密尔顿图，我们只给出了汉密尔顿图存在的充分条件和必要条件。仍没有找到充分必要条件。
(9)掌握平面图的概念及判定平面图的几种方法。
(10)掌握树的定义和性质并利用握手定理求树中结点的度数，会求连通图的生成树，用 Kruskal
算法求最小生成树。
(11)掌握根树、有序树,m叉树的概念，任何一棵有序树都可以改写成为二叉树。
