1
西安电子科技大学计算机学院 毛立强
lqmao@mail.xidian.edu.cn
西安电子科技大学计算机学院
西安电子科技大学计算机学院
离
散
数
学
离
散
数
学
主
讲
毛
立
强
主
讲
毛
立
强
2
西安电子科技大学计算机学院 毛立强
lqmao@mail.xidian.edu.cn
图论
图的基本概念
路径与回路
图的矩阵表示
二部图
平面图
树和有向树
3
西安电子科技大学计算机学院 毛立强
lqmao@mail.xidian.edu.cn
树
一个连通且无简单回路的无向图称为无向树，简称为树
(tree)。树中次数为1的结点称为树叶(leaf)，次数大于1的结点
称为分枝点或内部结点。一个无向图的各连通分图都是树
时，称该无向图为森林(forest)。树也是森林。
4
西安电子科技大学计算机学院 毛立强
lqmao@mail.xidian.edu.cn
树
给定图T，以下关于树的定义是等价的：
¾ 无简单回路的连通图；
¾ 无简单回路且m＝n－1，其中m是边数，n是结点数；
¾ 连通且m＝n－1；
¾ 无简单回路，但增加一条新边，得到且仅得到一条基本回
路；
¾ 连通，但删去任一边后便不连通(n≥2)；
¾ 每一对结点之间有且仅有一条基本路径(n≥2) 。
最大无回路图
最小连通图
5
西安电子科技大学计算机学院 毛立强
lqmao@mail.xidian.edu.cn
树
证明：采用轮转法。
无简单回路的连通图=>无简单回路且m＝n－1
在图T中，对n作归纳，当n＝1时，m＝0，则m＝n－1；
n＝2时，连通无简单回路，边数m＝1，则m＝n-1成立。
假设n＝k-1时命题成立，当n＝k时，因为无简单回路且
连通，故至少有一条边其一个端点u的次数为1。设该边为
(u,w)，删去结点u及其关联边(u,w) ，便得到一个k-1个结点的
连通无简单回路图T’，由归纳假设，图T’的边数为m’=n’-
1=(k-1)-1=k-2，于是再将结点u以及关联边(u,w)加到图T’中得
到原图T，此时T的边数为m=m’+1=(k-2)+1=k-1，结点数
n=n’+1=(k-1)+1=k，故m=n-1成立。
