第 7章 图论
7.1 无向图及有向图
7.2 通路、回路与连通性
7.3 图的矩阵表示
7.4 欧拉（ Euler）图
7.5 哈密尔顿（ Hamilton）图
7.6 二部图
7.7 平面图
7.8 树第 7章 图论图论的创始人是瑞士数学家欧拉，他于 1736
年首次建立“图”模型，解决了哥尼斯堡七桥问题,
图论是一个新的数学分支,也是一门很有实用价值的学科,它在自然科学、社会科学等领域均有很多应用,近年来它受计算机科学蓬勃发展的刺激，
发展极其迅速，应用范围不断拓展，已渗透到诸如语言学、逻辑学、物理学、化学、电子信息工程、计算机科学以及数学的其他分支中，特别是在计算机科学中，如形式语言、数据结构、分布式系统、操作系统等方面均扮演着重要的角色,
7.1 无向图及有向图
7.1.1图的概念
7.1.2度数与握手定理
7.1.3子图与补图
7.1.4图的同构
7.1.1图的概念一般几何上将图定义成空间一些点（顶点）
和连接这些点的线（边）的集合,图论中将图定义为一个二元组 G=〈 V,E〉,其中 V表示顶点的集合，
E表示边的集合,这样 下图 可表示为
V={v1,v2,v3,v4},E={e1,e2,e3,e4,e5,e6}.
7.1.1图的概念定义 7.1-1 设 A,B为任意的两个集合，称
{{a,b}|a∈ A∧ b∈ B}
为 A与 B的无序积，记作 A&B.
定义 7.1-2 一个无向图是一个有序的二元组〈 V，
E〉,记作 G，其中
（ 1） V（ ≠φ）称为顶点集，其元素称为顶点或结点；
（ 2） E称为边集，它是无序积 V&V的多重子集，
其元素称为无向边，简称边,
7.1.2度数与握手定理
1.顶点的度数设无向图 G=〈 V,E〉,顶点 vi的度数记为 d(vi),是指与 vi
相关联的边的条数,
在有向图 D＝〈 V,E〉中，以顶点 v为始点引出的边的条数，称为该顶点的出度,记为 d+(v)；以顶点 v为终点引入的边的条数，称为该顶点的入度,记为 d-(v)；而顶点的出度数与入度数之和称为该顶点的度数，简称度，记为 d(v)，
即
d(v)＝ d+(v)+d-(v).
7.1.2度数与握手定理
2.握手定理定理 7.1-1 (握手定理 )图 G=〈 V,E〉为任意无向图，其中 V={v1,v2,…,v n},|E|=m(m为边数 )，此时有
∑ d(vi)=2m,
即图中结点的度数之和等于边数的两倍,
n
i=1
7.1.2度数与握手定理定理 7.1-2 设 D=〈 V,E〉为任意有向图，
V={v1,v2,…,v n},|E|=m，此时有
∑d(vi)=2m
且 ∑d+(vi)= ∑d-(vi)= m.
推论 任何图 (无向的或有向的 )中，奇度数顶点的个数是偶数,
n
i=1
n
i=1
n
i=1
7.1.3子图与补图
1.子图定义 7.1-4 设 G=〈 V,E〉,G′=〈 V′,E′〉是两个图,若
V′ V,且 E′ E,则称 G′是 G的子图,G是 G′的母图，记作 G′
G.
若 G′ G且 G′≠G(即 V′ V或 E′ E)，则称 G′是 G的真子图,
若 G′ G且 V′= V，则称 G′是 G的生成子图,
设 V1 V且 V1≠φ，以 V1为顶点集，以两端点均在 V1中的全体边为边集的 G的子图，称为 V1导出的导出子图,
设 E1 E,且 E1≠φ，以 E1为边集，以 E1中边关联的顶点的全体为顶点集的 G的子图，称为 E1导出的导出子图,
7.1.3子图与补图
2.补图定义 7.1-5 设 G=〈 V,E〉是 n阶无向简单图,以 V为顶点，以所有能使 G成为完全图
Kn的添加边组成的集合为边集的图，称为 G
相对于完全图 Kn的补图，简称 G的补图，记作 G.
7.1.4图的同构图是表达事物之间关系的工具,在画图时，由于顶点位置的不同，边的直、曲不同，同一个事物之间的关系可能画出不同形状的图来，因而引出了图同构的概念,
定义 7.1-6 设两个无向图 G1=〈 V1,E1〉,G2=
〈 V2,E2〉，如果存在双射函数 θ:V1→V 2，使得对于任意的 e=(vi,vj)∈ E1当且仅当 e′=(θ(vi),θ(vj))∈ E2,
并且 e与 e′的重数相同，则称 G1与 G2是同构的，记作 G1≌ G2.
7.2 通路、回路与连通性
7.2.1 通路与回路
7.2.2 图的连通性
7.2.3 点割集与边割集
7.2 通路、回路与连通性在现实世界中,常常要考虑这样一个问题：如何从一个图 G中的给定的结点出发，
沿着一些边连续移动达到另一个指定的结点，这种依次由结点和边组成的序列，就形成通路的概念,
7.2.1 通路与回路定义 7.2-1 给定图 G=〈 V,E〉,设 v0，
v1,…,vn∈ V,e1,e2,…,en∈ E,其中 ei
是关联结点 vi-1,vi的边,交替序列
v0e1v1e2…e nvn称为联结点 v0到 vn的通路,
v0和 vn分别称作通路的起点和终点，当
v0=vn时,这条路称作回路,
7.2.1 通路与回路定理 7.2-1 在一个 n阶图中，若从顶点 vi到 vj存在通路
(vi≠vj)，则从 vi到 vj存在长度小于等于
n-1的通路,
推论 在一个 n阶图中，若从顶点 vi到 vj存在通路 (vi≠vj)，
则从 vi到 vj存在长度小于等于 n-1的初级通路,
定理 7.2-2 在一个 n阶图中，若 vi到自身存在回路，则从 vi到自身存在长度小于等于 n的回路,
推论 在一个 n阶图中，若 vi到自身存在一个简单回路，
则从 vi到自身存在长度小于等于 n的初级回路,
7.2.2图的连通性
1.无向图的连通性定义 7.2-2 在一个无向图 G中，若从顶点 vi到
vj存在通路（当然从 vj到 vi也存在通路），则称 vi与
vj是连通的,规定 vi到自身总是连通的,
设 vi,vj为无向图 G中的任意两点，若 vi与 vj是连通的，则称 vi与 vj之间长度最短的通路为 vi与 vj之间的短程线，短程线的长度称为 vi与 vj之间的距离，
记作 d(vi,vj).若 vi与 vj不连通，规定 d(vi,vj) = ∞.
7.2.2图的连通性定义 7.2-3 若无向图 G是平凡图，或 G
中任意两顶点都是连通的，则称 G是连通图；
否则，称 G是非连通图,
定理 7.2-3 无向图中顶点之间的连通关系是顶点集上的等价关系,
7.2.2图的连通性
2.有向图的连通性定义 7.2-4 在一个有向图 D中，若从顶点 vi到 vj存在通路，则称 vi可达 vj.规定 vi到自身总是可达的,
定义 7.2-5 一个有向图，如果忽略其边的方向后得到的无向图是连通的，则称此有向图为连通图；否则称为非连通图,
定义 7.2-6 一个有向连通图 G，如果其任何两顶点间均是相互可达的，则称图 G是强连通的；如果其任何两顶点间至少存在一个方向是可达的，则称图 G是单向连通的；
如果忽略边的方向后其无向图是连通的，则称图 G是弱连通的,
7.2.2图的连通性定理 7.2-4 一个有向图 D是强连通的，
当且仅当 D中存在一条回路，它至少经过每个顶点一次,
推论 若有向图 D中存在经过每个顶点至少一次的通路，则 D是单向连通的,
7.2.3点割集与边割集对于连通图，常常由于删除了图中的一些顶点或边，
而影响了图的连通性,
定义 7.2-7 设无向图 G=〈 V,E〉 为连通图，若有点集 V1 V，使图 G删除了 V1的所有顶点后，所得的子图是非连通图；而删除了 V1的任何真子集后，所得到的子图仍然是连通图，则称 V1是 G的一个点割集,若某一个顶点构成一个点割集，则称该顶点为割点,
定义 7.2-8 设无向图 G=〈 V,E〉 为连通图，若有边集 E1 E，使图 G删除了 E1的所有边后得的子图是非连通图；而删除了 E1的任何真子集后，所得到的子图仍然是连通图，则称 E1是 G的一个边割集,若某一条边构成一个边割集，则称该边为割边 (或桥 ).
7.3 图的矩阵表示
7.3.1 邻接矩阵
7.3.2 可达矩阵
7.3.3 完全关联矩阵
7.3图的矩阵表示图除了用图形表示外，还可以用矩阵表示,图的矩阵表示架起了图论与矩阵之间的桥梁，它一方面使我们可以借助于矩阵的理论和分析方法来研究图论中的问题，特别它将图的一些问题转化为矩阵运算的问题，更适合于计算机进行处理,顺便指出，由于矩阵的行列有固定的顺序，因此在用矩阵表示图之前，必须将图的结点和边（如果需要）进行编号,在本节主要讨论无向图、有向图的邻接矩阵，有向图的可达矩阵，图的关联矩阵,
有关矩阵的基本知识可以参考相关书籍,
7.3.1邻接矩阵定义 7.3-1 设 G=〈 V,E〉为简单图，
它有 n个结点 V={v1,v2,…,vn}，则 n阶方阵
A(G)=(aij)称为 G的邻接矩阵，其中
1,vi邻接 vj
aij=
0,vi不邻接 vj或 i=j.
7.3.2可达矩阵定义 7.3-2 令 G=〈 V,E〉是一个简单有向图,|V|=n，假定 G的结点已编序，即
V={v1,v2,…,v n}，定义一个 n× n矩阵 P(pij).其中
1，从 vi到 vj至少存在一条路
pij=
0，从 vi到 vj不存在路,
称矩阵 P是图 G的可达矩阵,
7.3.3完全关联矩阵对于一个无向图 G，除了可用邻接矩阵以外，
还对应着一个称为图 G的完全关联矩阵，假定图 G
无自回路，如因某种运算得到自回路，则将它删去,
定义 7.3-3 给定无向图 G，令 v1,v2,…,v n和
e1,e2,…,e m分别记为 G的结点和边，则矩阵
M(G)=(mij)，其中
1,若 vi关联 ej
mij =,
0,若 vi不关联 ej
称 M(G)为完全关联矩阵,
7.3.3完全关联矩阵定义 7.3-4 给定简单有向图 G=〈 V，
E〉,V={v1,v2,…,v n},E={e1,e2,…,e m}，
n× m阶矩阵 M(G)=(mij)，其中
1,在 G中 vi是 ej的起点
mij= -1，在 G中 vi是 ej的终点,
0，在 G中 vi不关联 ej
称 M(G)为 G的完全关联矩阵,
7.4 欧拉（ Euler）图定义 7.4-1 给定无孤立点图 G，若存在一条路，
经过图中每边一次且仅一次，该条路称为欧拉通路（欧拉迹）；若存在一条回路，经过图中的每边一次且仅一次，该回路称为欧拉回路（欧拉闭迹）,
具有欧拉回路的图称为欧拉图,
具有欧拉通路的图不能称为欧拉图，我们可以称为半欧拉图,
定理 7.4-1 无向图 G具有一条欧拉路，当且仅当 G是连通的，且有零个或两个奇数度结点,
推论 无向图 G具有一条欧拉回路，当且仅当
G是连通的，并且所有结点度数为偶数,
7.4 欧拉（ Euler）图定义 7.4-2 给定有向图 G，通过每边一次且仅一次的一条单向路 (回路 )，称作单向欧拉路 (回路 ).
定理 7.4-2 有向图 G具有一条单向欧拉回路，
当且仅当是连通的，且每个结点的入度等于出度,
一个有向图 G具有单向欧拉路，当且仅当是连通的，而且除两个结点外，每个结点的入度等于出度，但这两个结点中，一个结点的入度比出度大 1.
另一个结点的入度比出度小 1.
7.5哈密尔顿（ Hamilton）图与欧拉回路非常类似的问题是哈密尔顿回路问题,1859年威廉 ·哈密尔顿爵士在给他的朋友的一封信中，首先谈到关于十二面体的一个数学游戏，能不能在 下页图 中找到一条回路，使它含有这个图的所有结点？
他把结点看作是一座城市，联结两个结点的边看成是交通线，于是它的问题是能不能找到旅行路线，沿着交通线经过每一个城市恰好一次，再回到原来的出发地？他把这个问题称为周游世界问题,
7.5哈密尔顿（ Hamilton）图
7.5哈密尔顿（ Hamilton）图定义 7.5-1 给定图 G，若存在一条路经过图中的每一个结点恰好一次，这条路称作哈密尔顿路,
若存在一条回路，经过图中的每一个结点恰好一次，这个回路称作哈密尔顿回路,
具有哈密尔顿回路的图称为哈密尔顿图,
定理 7.5-1 若图 G=〈 V,E〉具有哈密尔顿回路，则对于结点集 V的每一个非空子集 S均有
W(G-S)≤|S|成立,其中 W(G-S)是 G-S中连通分支数,
7.5哈密尔顿（ Hamilton）图定理 7.5-2 设 G是具有 n个结点的简单图，如果 G中每一对结点的度数之和大于等于 n-1，则在 G中存在一条哈密尔顿路,
定理 7.5-3 设图 G是具有 n个结点的简单图，如果 G中每一对结点的度数大于等于 n，则在 G中存在一条哈密尔顿回路,
定义 7.5-2 给定图 G=〈 V,E〉 有 n个结点，若将图 G
中度数之和至少是 n的非邻接结点连接起来得到图 G′，对图 G′重复上述步骤，直到不再有这样的结点为止，所得的图称为原图 G的闭包，记作 C(G).
定理 7.5-4 当且仅当一个简单图的闭包是哈密尔顿图时，这个简单图是哈密尔顿图,
7.6 二部图二部图是一类十分重要的数学模型，有着许多应用，很多实际问题都可以使用二部图来解决，
如资源分配、任务派遣、择偶等,本节讨论的图均为无向图,
定义 7.6-1 若能将无向图 G=〈 V,E〉 的结点集 V划分成两个子集 V1和 V2(V1∩V2=φ)，使得 G中任何一条边的两个端点一个属于 V1，另一个属于
V2，则称 G为二部图 (也称为偶图 ).V1,V2称为互补结点子集，此时可将 G记成 G=〈 V1,V2,E〉,
定理 7.6-1 一个无向图 G=〈 V,E〉 是二部图当且仅当 G中无奇数长度的回路,
7.7平面图
7.7.1平面图的概念
7.7.2欧拉公式
7.7.3平面图的判断
7.7平面图在现实生活中，常常要画一些图形，希望边与边之间尽量减少相交的情况，例如，
印刷线路板的布线，交通道路的设计等,如无特殊声明，本节所说图 G均指无向图,
7.7.1平面图的概念定义 7.7-1 一个图 G如果能以这样的方式画在平面上：除顶点处外没有边交叉出现，则称 G为平面图,画出的没有边交叉出现的图称为 G的一个平面嵌入或 G的一个平图,
7.7.1平面图的概念定义 7.7-2 设 G是一个连通的平面图 (指
G的某个平面嵌入 ),G的边将 G所在的平面划分成若干个区域，每个区域称为 G的一个面，记成 R.其中面积无限的区域称为无限面或外部面，常记成 R0，面积有限的区域称为有限面或内部面，包围每个面的所有边所构成的回路（可能是初级回路或简单回路，也可能是复杂回路,）称为该面的边界，边界的长度称为该面的次数,R的次数记为 d(R).
7.7.1平面图的概念定理 7.7-1 在一个平面图 G中，所有面的次数之和都等于边数 m的 2倍，即
∑ d(Ri)=2m，
其中,r为面数,
r
i=1
7.7.2欧拉公式平面图的重要性质是满足欧拉公式,
定理 7.7-2 设 G为任意的连通的平面图，则有 n-m+r=2
成立,其中,n为 G中顶点数,m为边数,r为面数,
该定理中的公式称为欧拉公式,
定理 7.7-3 设 G为连通的平面图，且每个面的次数至少为 l(l≥3)，则
l
m≤ (n-2),
l-2
其中,n为 G中顶点数,m为边数,
7.7.2欧拉公式定理 7.7-4 设 G为连通的简单平面图
(n≥3)，则 m≤3n-6.
定理 7.7-5 设 G为连通的简单的平面图，
则 G中至少有一个顶点 v，有 d(v)≤5.
7.7.3平面图的判断下面讨论平面图的判断问题,
在下图 (1)中，从左到右的变换称为消去 2度顶点 w.下图 (2)中从左到右的变换称为插入 2度顶点 w.
显然，在图 G中消去和插入 2度顶点都不会影响图
G的平面性,
7.7.3平面图的判断定义 7.7-3 如果两个图 G1和 G2同构，或经过反复插入或消去 2度顶点后同构，则称 G1与 G2同胚,
定义 7.7-4 图 G中相邻顶点 u,v之间的初等收缩由下面方法给出：删除边 (u,v)，用新的顶点 w
取代 u,v，使 w关联 u,v关联的一切边 (除 (u,v)外 ).
定理 7.7-6 一个图是平面图当且仅当它不含与
K5同胚子图，也不含与 K3,3同胚子图,
定理 7.7-7 一个图是平面图当且仅当它没有可以收缩到 K5的子图，也没有可以收缩到 K3,3的子图,
7.8 树
7.8.1 无向树
7.8.2 生成树
7.8.3 根树及应用
7.8 树树是图论中的一个重要概念，它在许多学科，特别是在计算机学科中得到了广泛的应用,本节中所谈回路均指简单回路或初级回路，而不含复杂回路（有重复边出现的回路）,
7.8.1 无向树定义 7.8-1 连通而不含回路的无向图称为无向树，简称树，常用 T表示树,
若一个无向图的连通分支数大于等于 2，
且每个连通分支均是树,则称此非连通无向图为森林,平凡图称为平凡树,
设 T=〈 V,E〉为一棵无向树,v∈ V，
若 d(v)=1，则称 v为 T的树叶,若 d(v)≥2，则称 v为 T的分支点,
7.8.1 无向树定理 7.8-1 给定图 T，以下关于树的定义是等价的：
(1)无回路的连通图；
(2)无回路且 m=n-1，其中 m为边数,n为结点数；
(3)连通且 m=n-1；
(4)无回路且增加一条新边，得到一个且仅一个回路；
(5)连通且删去任何一个边后不连通；
(6)每一对结点之间有且仅有一条通路,
7.8.1 无向树定理 7.8-2 设 T=〈 V,E〉是 n阶非平凡的树，则 T中至少有 2片树叶,
7.8.2生成树定义 7.8-2 设 G=<V,E>是无向连通图,T是 G
的生成子图，并且 T是树，则称 T是 G的生成树，
G在 T中的边称为 T的树枝,
定理 7.8-3 任何连通图 G至少存在一棵生成树,
定义 7.8-3 设无向连通带权图 G=〈 V,E,W〉,
T是 G的一棵生成树,T各边带权之和称为 T的权，
记作 W(T).G的所有生成树中带权最小的生成树称为最小生成树,
7.8.3根树及应用
1.根树的定义一个有向图 D，如果略去有向边的方向所得无向图为一棵无向树，则称 D为有向树,在有向树中，最重要的是根树,
定义 7.8-4 一棵非平凡的有向树，如果有一个顶点的入度为 0，其余顶点的入度均为 1，则称此有向树为根树,入度为 0的顶点称为树根；入度为 1、出度为 0的顶点称为树叶；入度为 1、出度大于 0的顶点称为内点，内点和树根统称为分支点,
7.8.3根树及应用定义 7.8-5 设 T为一棵根树,a为 T中一个顶点，
且 a不是树根，称 a及其后代导出的子图 T′为 T的以
a为根的子树，简称根子树,
定义 7.8-6 如果将根树每一层上的顶点都规定次序，这样的根树称为有序树,
7.8.3根树及应用
2.根树的分类根据每个分支点的儿子数以及是否有序，可将根树分成若干类,
定义 7.8-7 设 T为一棵根树，
(1)若 T的每个分支点至多有 r个儿子，则称 T为 r元树；
(2)若 T的每个分支点都恰好有 r个儿子，则称 T为 r元正则树；
(3)若 r元树 T是有序的，则称 T是 r元有序树；
(4)若 r元正则树 T是有序的，则称 T是 r元有序正则树；
(5)若 T是 r元正则树，且所有树叶的层数相同，都等于树高，则称 T为 r元完全正则树；
(6)若 r元完全正则树 T是有序树，则称 T是 r元有序完全正则树,
7.8.3根树及应用
3.最优 2元树的定义定义 7.8-8 设 2元树 T有 t片树叶，分别带权为 w1,w2,…,wi,…,wt(wi为实数，
i=1,2,…,t),称
W(T)=∑ wiL(wi)为 T的权，其中 L(wi)为带权 wi
的树叶 vi的层数,在所有的带权 w1,w2,…,
wt的 2元树中，带权最小的 2元树称为最优 2
元树,
t
i=1
7.8.3根树及应用
4.Huffman算法求最优树的算法是由 Huffman给出的,
Huffman算法：
给定实数 w1,w2,…,wt，且 w1≤w2≤…≤w t，
(1)连接以 w1,w2为权的两片树叶，得一分支点，其权为 w1+w2；
(2)在 w1+w2,w3,…,wt中选出两个最小的权，连接它们对应的顶点 (不一定都是树叶 )，得分支点及其所带的权；
(3)重复 (2)，直到形成一棵有 t-1个分支点,t片树叶的树为止,
7.8.3根树及应用
5.根树的 3种行遍法对于一棵根树的每个顶点都访问一次且仅一次称为行遍或周游一棵树,对于 2元有序正则树主要有以下 3种行遍方法,
(1)中序行遍法其访问次序为：左子树，树根，右子树，在每棵子树中也按同一次序行遍,
(2)前序行遍法其访问次序为：树根，左子树，右子树，在每棵子树中也按同一次序行遍,
(3)后序行遍法其访问次序为：左子树，右子树，树根，在每棵子树中也按同一次序行遍,
本章小结本章主要讨论了：
(1) 图的基本概念与表示，边与点之间的关系，各种不同的图,
(2) 路与回路的概念，图的连通性,
(3) 图的邻接矩阵、可达性矩阵以及完全关联矩阵的表示和相关性质,
(4) 欧拉图的定义及其判断,
(5) 哈密尔顿图的定义及判断是否为哈密尔顿图的充分条件和必要条件,
(6) 二部图的基本概念和判断方法,
(7) 平面图的基本概念、性质，欧拉公式和判断方法,
(8) 树、有向树、无向树、子树、生成树等的基本概念和性质及二叉树的应用,
7.1 无向图及有向图
7.2 通路、回路与连通性
7.3 图的矩阵表示
7.4 欧拉（ Euler）图
7.5 哈密尔顿（ Hamilton）图
7.6 二部图
7.7 平面图
7.8 树第 7章 图论图论的创始人是瑞士数学家欧拉，他于 1736
年首次建立“图”模型，解决了哥尼斯堡七桥问题,
图论是一个新的数学分支,也是一门很有实用价值的学科,它在自然科学、社会科学等领域均有很多应用,近年来它受计算机科学蓬勃发展的刺激，
发展极其迅速，应用范围不断拓展，已渗透到诸如语言学、逻辑学、物理学、化学、电子信息工程、计算机科学以及数学的其他分支中，特别是在计算机科学中，如形式语言、数据结构、分布式系统、操作系统等方面均扮演着重要的角色,
7.1 无向图及有向图
7.1.1图的概念
7.1.2度数与握手定理
7.1.3子图与补图
7.1.4图的同构
7.1.1图的概念一般几何上将图定义成空间一些点（顶点）
和连接这些点的线（边）的集合,图论中将图定义为一个二元组 G=〈 V,E〉,其中 V表示顶点的集合，
E表示边的集合,这样 下图 可表示为
V={v1,v2,v3,v4},E={e1,e2,e3,e4,e5,e6}.
7.1.1图的概念定义 7.1-1 设 A,B为任意的两个集合，称
{{a,b}|a∈ A∧ b∈ B}
为 A与 B的无序积，记作 A&B.
定义 7.1-2 一个无向图是一个有序的二元组〈 V，
E〉,记作 G，其中
（ 1） V（ ≠φ）称为顶点集，其元素称为顶点或结点；
（ 2） E称为边集，它是无序积 V&V的多重子集，
其元素称为无向边，简称边,
7.1.2度数与握手定理
1.顶点的度数设无向图 G=〈 V,E〉,顶点 vi的度数记为 d(vi),是指与 vi
相关联的边的条数,
在有向图 D＝〈 V,E〉中，以顶点 v为始点引出的边的条数，称为该顶点的出度,记为 d+(v)；以顶点 v为终点引入的边的条数，称为该顶点的入度,记为 d-(v)；而顶点的出度数与入度数之和称为该顶点的度数，简称度，记为 d(v)，
即
d(v)＝ d+(v)+d-(v).
7.1.2度数与握手定理
2.握手定理定理 7.1-1 (握手定理 )图 G=〈 V,E〉为任意无向图，其中 V={v1,v2,…,v n},|E|=m(m为边数 )，此时有
∑ d(vi)=2m,
即图中结点的度数之和等于边数的两倍,
n
i=1
7.1.2度数与握手定理定理 7.1-2 设 D=〈 V,E〉为任意有向图，
V={v1,v2,…,v n},|E|=m，此时有
∑d(vi)=2m
且 ∑d+(vi)= ∑d-(vi)= m.
推论 任何图 (无向的或有向的 )中，奇度数顶点的个数是偶数,
n
i=1
n
i=1
n
i=1
7.1.3子图与补图
1.子图定义 7.1-4 设 G=〈 V,E〉,G′=〈 V′,E′〉是两个图,若
V′ V,且 E′ E,则称 G′是 G的子图,G是 G′的母图，记作 G′
G.
若 G′ G且 G′≠G(即 V′ V或 E′ E)，则称 G′是 G的真子图,
若 G′ G且 V′= V，则称 G′是 G的生成子图,
设 V1 V且 V1≠φ，以 V1为顶点集，以两端点均在 V1中的全体边为边集的 G的子图，称为 V1导出的导出子图,
设 E1 E,且 E1≠φ，以 E1为边集，以 E1中边关联的顶点的全体为顶点集的 G的子图，称为 E1导出的导出子图,
7.1.3子图与补图
2.补图定义 7.1-5 设 G=〈 V,E〉是 n阶无向简单图,以 V为顶点，以所有能使 G成为完全图
Kn的添加边组成的集合为边集的图，称为 G
相对于完全图 Kn的补图，简称 G的补图，记作 G.
7.1.4图的同构图是表达事物之间关系的工具,在画图时，由于顶点位置的不同，边的直、曲不同，同一个事物之间的关系可能画出不同形状的图来，因而引出了图同构的概念,
定义 7.1-6 设两个无向图 G1=〈 V1,E1〉,G2=
〈 V2,E2〉，如果存在双射函数 θ:V1→V 2，使得对于任意的 e=(vi,vj)∈ E1当且仅当 e′=(θ(vi),θ(vj))∈ E2,
并且 e与 e′的重数相同，则称 G1与 G2是同构的，记作 G1≌ G2.
7.2 通路、回路与连通性
7.2.1 通路与回路
7.2.2 图的连通性
7.2.3 点割集与边割集
7.2 通路、回路与连通性在现实世界中,常常要考虑这样一个问题：如何从一个图 G中的给定的结点出发，
沿着一些边连续移动达到另一个指定的结点，这种依次由结点和边组成的序列，就形成通路的概念,
7.2.1 通路与回路定义 7.2-1 给定图 G=〈 V,E〉,设 v0，
v1,…,vn∈ V,e1,e2,…,en∈ E,其中 ei
是关联结点 vi-1,vi的边,交替序列
v0e1v1e2…e nvn称为联结点 v0到 vn的通路,
v0和 vn分别称作通路的起点和终点，当
v0=vn时,这条路称作回路,
7.2.1 通路与回路定理 7.2-1 在一个 n阶图中，若从顶点 vi到 vj存在通路
(vi≠vj)，则从 vi到 vj存在长度小于等于
n-1的通路,
推论 在一个 n阶图中，若从顶点 vi到 vj存在通路 (vi≠vj)，
则从 vi到 vj存在长度小于等于 n-1的初级通路,
定理 7.2-2 在一个 n阶图中，若 vi到自身存在回路，则从 vi到自身存在长度小于等于 n的回路,
推论 在一个 n阶图中，若 vi到自身存在一个简单回路，
则从 vi到自身存在长度小于等于 n的初级回路,
7.2.2图的连通性
1.无向图的连通性定义 7.2-2 在一个无向图 G中，若从顶点 vi到
vj存在通路（当然从 vj到 vi也存在通路），则称 vi与
vj是连通的,规定 vi到自身总是连通的,
设 vi,vj为无向图 G中的任意两点，若 vi与 vj是连通的，则称 vi与 vj之间长度最短的通路为 vi与 vj之间的短程线，短程线的长度称为 vi与 vj之间的距离，
记作 d(vi,vj).若 vi与 vj不连通，规定 d(vi,vj) = ∞.
7.2.2图的连通性定义 7.2-3 若无向图 G是平凡图，或 G
中任意两顶点都是连通的，则称 G是连通图；
否则，称 G是非连通图,
定理 7.2-3 无向图中顶点之间的连通关系是顶点集上的等价关系,
7.2.2图的连通性
2.有向图的连通性定义 7.2-4 在一个有向图 D中，若从顶点 vi到 vj存在通路，则称 vi可达 vj.规定 vi到自身总是可达的,
定义 7.2-5 一个有向图，如果忽略其边的方向后得到的无向图是连通的，则称此有向图为连通图；否则称为非连通图,
定义 7.2-6 一个有向连通图 G，如果其任何两顶点间均是相互可达的，则称图 G是强连通的；如果其任何两顶点间至少存在一个方向是可达的，则称图 G是单向连通的；
如果忽略边的方向后其无向图是连通的，则称图 G是弱连通的,
7.2.2图的连通性定理 7.2-4 一个有向图 D是强连通的，
当且仅当 D中存在一条回路，它至少经过每个顶点一次,
推论 若有向图 D中存在经过每个顶点至少一次的通路，则 D是单向连通的,
7.2.3点割集与边割集对于连通图，常常由于删除了图中的一些顶点或边，
而影响了图的连通性,
定义 7.2-7 设无向图 G=〈 V,E〉 为连通图，若有点集 V1 V，使图 G删除了 V1的所有顶点后，所得的子图是非连通图；而删除了 V1的任何真子集后，所得到的子图仍然是连通图，则称 V1是 G的一个点割集,若某一个顶点构成一个点割集，则称该顶点为割点,
定义 7.2-8 设无向图 G=〈 V,E〉 为连通图，若有边集 E1 E，使图 G删除了 E1的所有边后得的子图是非连通图；而删除了 E1的任何真子集后，所得到的子图仍然是连通图，则称 E1是 G的一个边割集,若某一条边构成一个边割集，则称该边为割边 (或桥 ).
7.3 图的矩阵表示
7.3.1 邻接矩阵
7.3.2 可达矩阵
7.3.3 完全关联矩阵
7.3图的矩阵表示图除了用图形表示外，还可以用矩阵表示,图的矩阵表示架起了图论与矩阵之间的桥梁，它一方面使我们可以借助于矩阵的理论和分析方法来研究图论中的问题，特别它将图的一些问题转化为矩阵运算的问题，更适合于计算机进行处理,顺便指出，由于矩阵的行列有固定的顺序，因此在用矩阵表示图之前，必须将图的结点和边（如果需要）进行编号,在本节主要讨论无向图、有向图的邻接矩阵，有向图的可达矩阵，图的关联矩阵,
有关矩阵的基本知识可以参考相关书籍,
7.3.1邻接矩阵定义 7.3-1 设 G=〈 V,E〉为简单图，
它有 n个结点 V={v1,v2,…,vn}，则 n阶方阵
A(G)=(aij)称为 G的邻接矩阵，其中
1,vi邻接 vj
aij=
0,vi不邻接 vj或 i=j.
7.3.2可达矩阵定义 7.3-2 令 G=〈 V,E〉是一个简单有向图,|V|=n，假定 G的结点已编序，即
V={v1,v2,…,v n}，定义一个 n× n矩阵 P(pij).其中
1，从 vi到 vj至少存在一条路
pij=
0，从 vi到 vj不存在路,
称矩阵 P是图 G的可达矩阵,
7.3.3完全关联矩阵对于一个无向图 G，除了可用邻接矩阵以外，
还对应着一个称为图 G的完全关联矩阵，假定图 G
无自回路，如因某种运算得到自回路，则将它删去,
定义 7.3-3 给定无向图 G，令 v1,v2,…,v n和
e1,e2,…,e m分别记为 G的结点和边，则矩阵
M(G)=(mij)，其中
1,若 vi关联 ej
mij =,
0,若 vi不关联 ej
称 M(G)为完全关联矩阵,
7.3.3完全关联矩阵定义 7.3-4 给定简单有向图 G=〈 V，
E〉,V={v1,v2,…,v n},E={e1,e2,…,e m}，
n× m阶矩阵 M(G)=(mij)，其中
1,在 G中 vi是 ej的起点
mij= -1，在 G中 vi是 ej的终点,
0，在 G中 vi不关联 ej
称 M(G)为 G的完全关联矩阵,
7.4 欧拉（ Euler）图定义 7.4-1 给定无孤立点图 G，若存在一条路，
经过图中每边一次且仅一次，该条路称为欧拉通路（欧拉迹）；若存在一条回路，经过图中的每边一次且仅一次，该回路称为欧拉回路（欧拉闭迹）,
具有欧拉回路的图称为欧拉图,
具有欧拉通路的图不能称为欧拉图，我们可以称为半欧拉图,
定理 7.4-1 无向图 G具有一条欧拉路，当且仅当 G是连通的，且有零个或两个奇数度结点,
推论 无向图 G具有一条欧拉回路，当且仅当
G是连通的，并且所有结点度数为偶数,
7.4 欧拉（ Euler）图定义 7.4-2 给定有向图 G，通过每边一次且仅一次的一条单向路 (回路 )，称作单向欧拉路 (回路 ).
定理 7.4-2 有向图 G具有一条单向欧拉回路，
当且仅当是连通的，且每个结点的入度等于出度,
一个有向图 G具有单向欧拉路，当且仅当是连通的，而且除两个结点外，每个结点的入度等于出度，但这两个结点中，一个结点的入度比出度大 1.
另一个结点的入度比出度小 1.
7.5哈密尔顿（ Hamilton）图与欧拉回路非常类似的问题是哈密尔顿回路问题,1859年威廉 ·哈密尔顿爵士在给他的朋友的一封信中，首先谈到关于十二面体的一个数学游戏，能不能在 下页图 中找到一条回路，使它含有这个图的所有结点？
他把结点看作是一座城市，联结两个结点的边看成是交通线，于是它的问题是能不能找到旅行路线，沿着交通线经过每一个城市恰好一次，再回到原来的出发地？他把这个问题称为周游世界问题,
7.5哈密尔顿（ Hamilton）图
7.5哈密尔顿（ Hamilton）图定义 7.5-1 给定图 G，若存在一条路经过图中的每一个结点恰好一次，这条路称作哈密尔顿路,
若存在一条回路，经过图中的每一个结点恰好一次，这个回路称作哈密尔顿回路,
具有哈密尔顿回路的图称为哈密尔顿图,
定理 7.5-1 若图 G=〈 V,E〉具有哈密尔顿回路，则对于结点集 V的每一个非空子集 S均有
W(G-S)≤|S|成立,其中 W(G-S)是 G-S中连通分支数,
7.5哈密尔顿（ Hamilton）图定理 7.5-2 设 G是具有 n个结点的简单图，如果 G中每一对结点的度数之和大于等于 n-1，则在 G中存在一条哈密尔顿路,
定理 7.5-3 设图 G是具有 n个结点的简单图，如果 G中每一对结点的度数大于等于 n，则在 G中存在一条哈密尔顿回路,
定义 7.5-2 给定图 G=〈 V,E〉 有 n个结点，若将图 G
中度数之和至少是 n的非邻接结点连接起来得到图 G′，对图 G′重复上述步骤，直到不再有这样的结点为止，所得的图称为原图 G的闭包，记作 C(G).
定理 7.5-4 当且仅当一个简单图的闭包是哈密尔顿图时，这个简单图是哈密尔顿图,
7.6 二部图二部图是一类十分重要的数学模型，有着许多应用，很多实际问题都可以使用二部图来解决，
如资源分配、任务派遣、择偶等,本节讨论的图均为无向图,
定义 7.6-1 若能将无向图 G=〈 V,E〉 的结点集 V划分成两个子集 V1和 V2(V1∩V2=φ)，使得 G中任何一条边的两个端点一个属于 V1，另一个属于
V2，则称 G为二部图 (也称为偶图 ).V1,V2称为互补结点子集，此时可将 G记成 G=〈 V1,V2,E〉,
定理 7.6-1 一个无向图 G=〈 V,E〉 是二部图当且仅当 G中无奇数长度的回路,
7.7平面图
7.7.1平面图的概念
7.7.2欧拉公式
7.7.3平面图的判断
7.7平面图在现实生活中，常常要画一些图形，希望边与边之间尽量减少相交的情况，例如，
印刷线路板的布线，交通道路的设计等,如无特殊声明，本节所说图 G均指无向图,
7.7.1平面图的概念定义 7.7-1 一个图 G如果能以这样的方式画在平面上：除顶点处外没有边交叉出现，则称 G为平面图,画出的没有边交叉出现的图称为 G的一个平面嵌入或 G的一个平图,
7.7.1平面图的概念定义 7.7-2 设 G是一个连通的平面图 (指
G的某个平面嵌入 ),G的边将 G所在的平面划分成若干个区域，每个区域称为 G的一个面，记成 R.其中面积无限的区域称为无限面或外部面，常记成 R0，面积有限的区域称为有限面或内部面，包围每个面的所有边所构成的回路（可能是初级回路或简单回路，也可能是复杂回路,）称为该面的边界，边界的长度称为该面的次数,R的次数记为 d(R).
7.7.1平面图的概念定理 7.7-1 在一个平面图 G中，所有面的次数之和都等于边数 m的 2倍，即
∑ d(Ri)=2m，
其中,r为面数,
r
i=1
7.7.2欧拉公式平面图的重要性质是满足欧拉公式,
定理 7.7-2 设 G为任意的连通的平面图，则有 n-m+r=2
成立,其中,n为 G中顶点数,m为边数,r为面数,
该定理中的公式称为欧拉公式,
定理 7.7-3 设 G为连通的平面图，且每个面的次数至少为 l(l≥3)，则
l
m≤ (n-2),
l-2
其中,n为 G中顶点数,m为边数,
7.7.2欧拉公式定理 7.7-4 设 G为连通的简单平面图
(n≥3)，则 m≤3n-6.
定理 7.7-5 设 G为连通的简单的平面图，
则 G中至少有一个顶点 v，有 d(v)≤5.
7.7.3平面图的判断下面讨论平面图的判断问题,
在下图 (1)中，从左到右的变换称为消去 2度顶点 w.下图 (2)中从左到右的变换称为插入 2度顶点 w.
显然，在图 G中消去和插入 2度顶点都不会影响图
G的平面性,
7.7.3平面图的判断定义 7.7-3 如果两个图 G1和 G2同构，或经过反复插入或消去 2度顶点后同构，则称 G1与 G2同胚,
定义 7.7-4 图 G中相邻顶点 u,v之间的初等收缩由下面方法给出：删除边 (u,v)，用新的顶点 w
取代 u,v，使 w关联 u,v关联的一切边 (除 (u,v)外 ).
定理 7.7-6 一个图是平面图当且仅当它不含与
K5同胚子图，也不含与 K3,3同胚子图,
定理 7.7-7 一个图是平面图当且仅当它没有可以收缩到 K5的子图，也没有可以收缩到 K3,3的子图,
7.8 树
7.8.1 无向树
7.8.2 生成树
7.8.3 根树及应用
7.8 树树是图论中的一个重要概念，它在许多学科，特别是在计算机学科中得到了广泛的应用,本节中所谈回路均指简单回路或初级回路，而不含复杂回路（有重复边出现的回路）,
7.8.1 无向树定义 7.8-1 连通而不含回路的无向图称为无向树，简称树，常用 T表示树,
若一个无向图的连通分支数大于等于 2，
且每个连通分支均是树,则称此非连通无向图为森林,平凡图称为平凡树,
设 T=〈 V,E〉为一棵无向树,v∈ V，
若 d(v)=1，则称 v为 T的树叶,若 d(v)≥2，则称 v为 T的分支点,
7.8.1 无向树定理 7.8-1 给定图 T，以下关于树的定义是等价的：
(1)无回路的连通图；
(2)无回路且 m=n-1，其中 m为边数,n为结点数；
(3)连通且 m=n-1；
(4)无回路且增加一条新边，得到一个且仅一个回路；
(5)连通且删去任何一个边后不连通；
(6)每一对结点之间有且仅有一条通路,
7.8.1 无向树定理 7.8-2 设 T=〈 V,E〉是 n阶非平凡的树，则 T中至少有 2片树叶,
7.8.2生成树定义 7.8-2 设 G=<V,E>是无向连通图,T是 G
的生成子图，并且 T是树，则称 T是 G的生成树，
G在 T中的边称为 T的树枝,
定理 7.8-3 任何连通图 G至少存在一棵生成树,
定义 7.8-3 设无向连通带权图 G=〈 V,E,W〉,
T是 G的一棵生成树,T各边带权之和称为 T的权，
记作 W(T).G的所有生成树中带权最小的生成树称为最小生成树,
7.8.3根树及应用
1.根树的定义一个有向图 D，如果略去有向边的方向所得无向图为一棵无向树，则称 D为有向树,在有向树中，最重要的是根树,
定义 7.8-4 一棵非平凡的有向树，如果有一个顶点的入度为 0，其余顶点的入度均为 1，则称此有向树为根树,入度为 0的顶点称为树根；入度为 1、出度为 0的顶点称为树叶；入度为 1、出度大于 0的顶点称为内点，内点和树根统称为分支点,
7.8.3根树及应用定义 7.8-5 设 T为一棵根树,a为 T中一个顶点，
且 a不是树根，称 a及其后代导出的子图 T′为 T的以
a为根的子树，简称根子树,
定义 7.8-6 如果将根树每一层上的顶点都规定次序，这样的根树称为有序树,
7.8.3根树及应用
2.根树的分类根据每个分支点的儿子数以及是否有序，可将根树分成若干类,
定义 7.8-7 设 T为一棵根树，
(1)若 T的每个分支点至多有 r个儿子，则称 T为 r元树；
(2)若 T的每个分支点都恰好有 r个儿子，则称 T为 r元正则树；
(3)若 r元树 T是有序的，则称 T是 r元有序树；
(4)若 r元正则树 T是有序的，则称 T是 r元有序正则树；
(5)若 T是 r元正则树，且所有树叶的层数相同，都等于树高，则称 T为 r元完全正则树；
(6)若 r元完全正则树 T是有序树，则称 T是 r元有序完全正则树,
7.8.3根树及应用
3.最优 2元树的定义定义 7.8-8 设 2元树 T有 t片树叶，分别带权为 w1,w2,…,wi,…,wt(wi为实数，
i=1,2,…,t),称
W(T)=∑ wiL(wi)为 T的权，其中 L(wi)为带权 wi
的树叶 vi的层数,在所有的带权 w1,w2,…,
wt的 2元树中，带权最小的 2元树称为最优 2
元树,
t
i=1
7.8.3根树及应用
4.Huffman算法求最优树的算法是由 Huffman给出的,
Huffman算法：
给定实数 w1,w2,…,wt，且 w1≤w2≤…≤w t，
(1)连接以 w1,w2为权的两片树叶，得一分支点，其权为 w1+w2；
(2)在 w1+w2,w3,…,wt中选出两个最小的权，连接它们对应的顶点 (不一定都是树叶 )，得分支点及其所带的权；
(3)重复 (2)，直到形成一棵有 t-1个分支点,t片树叶的树为止,
7.8.3根树及应用
5.根树的 3种行遍法对于一棵根树的每个顶点都访问一次且仅一次称为行遍或周游一棵树,对于 2元有序正则树主要有以下 3种行遍方法,
(1)中序行遍法其访问次序为：左子树，树根，右子树，在每棵子树中也按同一次序行遍,
(2)前序行遍法其访问次序为：树根，左子树，右子树，在每棵子树中也按同一次序行遍,
(3)后序行遍法其访问次序为：左子树，右子树，树根，在每棵子树中也按同一次序行遍,
本章小结本章主要讨论了：
(1) 图的基本概念与表示，边与点之间的关系，各种不同的图,
(2) 路与回路的概念，图的连通性,
(3) 图的邻接矩阵、可达性矩阵以及完全关联矩阵的表示和相关性质,
(4) 欧拉图的定义及其判断,
(5) 哈密尔顿图的定义及判断是否为哈密尔顿图的充分条件和必要条件,
(6) 二部图的基本概念和判断方法,
(7) 平面图的基本概念、性质，欧拉公式和判断方法,
(8) 树、有向树、无向树、子树、生成树等的基本概念和性质及二叉树的应用,
