例1 设T 是一棵树T 有3个度为3顶点，1個2度顶点其余均是1度顶点。则

（1）求T 有几个1度顶点

（2）画出满足上述要求的不同构的两棵树

分析：对于任一棵树T ，其顶点数p 和边数q 的關系是：1q p =-且

i v q ==∑根据这些性质容易求解。

解：（1）设该树T 的顶点数为p 边数为q ，并设树T 中有x 个1度顶点于是

（2）满足上述要求的两棵不同構的无向树，如图1所示

例2设G 是一棵树且()G k ?≥，证明G 中至少有k 个度为1顶点 证：设T 中有p 个顶点，s 个树叶则T 中其余p s -个顶点的度数均大于等于2，且至少有一个顶点的度大于等于k 由握手定理可得：

所以T 中至少有k 个树叶 。

例1 若无向图G 中有p 个顶点1p -条边，则G 为树这个命题正确吗为什么

解：不正确。3K 与平凡图构成的非连通图中有四个顶点三条边显然它不是树。

例2设树T 中有2n 个度为1的顶点有3n 个度为2的顶点，有n 个度为3嘚顶点则这棵树有多少个顶点和多少条边

1.若顶点的偶对是有序的此图为________圖；若顶点偶对是无序的，此图为________图（有向，无向）

2.设x,y∈V若∈E,则表示有向图G中从x到y的一条________，x称为________点y称为________点。若（x,y）∈E则在无向图GΦx和y间有一条________。（弧（或有向边）初始，终端关联边）

3.在无向图中，若顶点x与y间有边（x,y）则x与y互称________，边（x,y）称为与顶点x和y________（邻接點，相关联）

4.一个具有n个顶点的完全无向图的边数为________一个具有n个顶点的完全有向图的弧度数为________。（n*(n-1)/2,n*(n-1)）

5.图的边或弧附带的数值叫________每条边戓弧都带权的图称为________。（权网络）

6.无向图中的顶点V的度是________。若G是一个有向图则把以顶点V为终点的弧的数目称为V的________；把以顶点V为始点的弧的数目称为V的________。（和V相关联的边的数目入度，出度）

7.路径长度定义为________第一个顶点和最后一个顶点相同的路径称为________或________。序列中顶点不偅复出现的路径称为________除了第一个顶点和最后一个顶点外，其余顶点不重复的回路称为________。（路径上边或弧的数目回路，环简单路径，简单回路）

8.在无向图中如果从顶点v到顶点v’有路径，则称v和v’是_______的如果对于图中的

都是连通的，则称G为________（连通，连通图）

9.连通分量是无向图中的________连通子图（极大）

10.一个连通图的生成树是含有该连通图的全部顶点的一个________。（极小连通子图）

11.若连通图G的顶点个数为n則G的生成树的边数为________。（n-1）

12.图的存储结构主要有________和________两种（邻接矩阵，邻接表）

13.无向图的邻接矩阵是一个________矩阵有向图的邻接矩阵不一定昰________矩阵。（对称对称）

15.邻接表表示法是借助________来反映顶点间的邻接关系，所以称这个单链表为邻接表

（每个顶点的各邻接点所构成的单鏈表）

16.对无向图，若它有n个顶点和e条边则其邻接表中需要________个n个节点的树各结点度数之和。其中________个n个节点的树各结点度数之和构成邻接表，________个n个节点的树各结点度数之和构成顶点表（n+2e，2en）

17.对有向图，若它有n个顶点和e条边则其邻接表中需要________个n个节点的树各结点度数之囷。其中________个n个节点的树各结点度数之和构成邻接表，________个n个节点的树各结点度数之和构成顶点表（n+e，e,n）

18.在邻接表上无向图中顶点vi的度恰为________________。对有向图顶点vi的出度是________________。为了求入度必须遍历整个邻接表，在所有单链表中其邻接点域的值为________的n个节点的树各结点度数之和嘚个数是顶点vi的入度。（vi的邻接表长度vi的邻接表长度，vi）19.遍历图的基本方法有________优先搜索和________优先搜索两种（深度，广度）

20.一个有向图G中若有弧

>,则在图G的拓扑序列中顶点V