图论复习

图论复习题

第一章 图

主要内容：

1．图的基本概念和基本定理（重点是完全图、二部图、图的同构、握手定理等） 2．轨道和圈（最长轨理论）

练习题目：

1．5阶无向完全图的边数为__10_____。

2．图G1和G2的结点和边分别存在一一对应关系是G1和G2同构的_充分必要条件

______。

3．图G1和G2的结点和边分别存在一一对应关系是G1和G2同构的_充分必要条件

______。

4．设无向简单图的顶点个数为n，则该图最多有_n(n-1)/2_ 条边。

5．一个有n个结点的图，最少有___1____个连通分支。

6．有三个顶点的所有互不同构的简单无向图有___4____个。

7．单连通无向图G有12条边，G中有2个1度结点，2个2度结点，3个4度结点，其余结点度数为3．求G中有多少个结点．试作一个满足该条件的简单无向图． 解：设G中有x各结点，则3度的结点有x-7 根据握手定理有，1x2+2x2+4x3+3x(x-7)=2x12 解得x=9,故G中有9个结点。 满

足

条

件

的

图

如

下

：

8．单连通无向图G有9条边，G中有4个3度结点，2个1度结点，其余结点度数为2．求G中有多少个结点．试作一个满足该条件的简单无向图．

9．面上有n个点S＝{x1,x2,……,xn}，其中任两个点之间的距离至少是1，证明在这n个点中距离为1的点对数不超过3n。（38题） 10．若图G是简单图， 且q?(p?1)(p?2)，则G连通。（42题）

211．如果G是具有m条边的n阶简单图，证明：若G的直径为2且△= n-2，则m≥2n-4。（50题）

12．证明：在任何图中，奇度点个数为偶数。（推论1.1） 13．证明：图G是二部图当且仅当G无奇圈。（定理1.2） 14．证明：每个顶点度数都大于等于2的简单图必有圈。（例1.9） 15．证明：每个顶点度数都大于等于3的简单图必有偶圈。（例1.11）

16．画出4个顶点的不同构的图（包括连通和不连通图）。

第二章 树

主要内容：

1．树的定义和简单性质； 2．树的几个等价条件；

3．生成树的个数（Cayley公式）

练习题目：

1．设树T中有2个3度顶点和3个4度顶点，其余的顶点都是树叶，则T中有____片树叶。 2. 一棵无向树的顶点数为n，则其边数为____，其结点度数之和是____。

3. 任何连通无向图G至少有____ 棵生成树，当且仅当G 是____ ，G的生成树只有一棵。 4. 证明：每棵非平凡树T至少有两个度为1的顶点。（例2.1） 5. 证明：如果一棵树仅有两个叶，则此树就是一条轨道。（2题）

6. 证明：在任何连通图中都会找到一条边或者一个点，把它删除后，所得子图仍连通。（20题）

7.写出6阶完全图的不同生成树个数以及不同构者个数。（22题）

第三章 平面图

主要内容：

1．平面图的定义和简单性质； 2．Euler公式及其应用。

练习题目：

1．3阶以上的极大平面图的面数和顶点数的关系为_______。

2．把平面分成x个区域，每两个区域都相邻，问x最大为_______。 4.每一个p?4的可平面图G至少有四个顶点的图不能超过5。

5.设G是有11个或更多结点的图，证明G或G（补图）是非平面图。（7题） 6.设w是平面图G的连通分支个数， 则?(G)??(G)??(G)?w?1（11题）

3．连通无向图G是（n，m）图，若G是平面图，则G有_______个面。

第四章 匹配理论及其应用

主要内容：

1．匹配的定义和简单性质；

2．二部图的匹配定理。

练习题目：

1．设G是具有二分划（X,Y）的二部图，则G含有饱和X中的每个顶点的匹配M当且仅当对

?S?X,|N(S)|?|S|. （Hall定理）

2.K次正则二部图有完备匹配。（推论4.1）

3.设G是具有二分划（X,Y）的简单二部图，且?(G)?完备匹配。

nn|X|=|Y|=n, 若?(G)?,则G有22

第五章 着色理论

主要内容：

1．边着色和点着色的定义和简单性质； 2．二部图的边色数定理。

练习题目：

1.下图的点色数为_______;边色数为_______。

?2．如果G是有奇数个顶点的有边正则图，则?(G)???1。（5题）

?3． 若G是2n+1个点的简单图，且边数m>n?(?是G的最大度)，则G的边色数?(G)???1。

（6题）

第六章Euler图和Hamilton图

主要内容：

Euler图和Hamilton图的定义和判定。

练习题目：

1. Hamilton图的必要条件（定理6.4）.

2．设n阶完全图有m条边，当_______时，图中存在欧拉回路。 3.构造一个欧拉图，其结点数n与边数m满足下列条件 （1）n，m的奇偶性一样的简单图。

（2）n，m的奇偶性相反的简单图。 如果不可能，请说明原因。

4. 有一个n人的团体（n?3），这n个人中相互认识的对数（两个人认识就算作一对）至少是

(n?1)(n?2)?2.

2证明： 这n个人可以圆桌而坐，使每个人与他相邻座位上的2个人认识。

四个算法

主要内容：

1．利用Dijkstra算法编程求解最短轨长度问题

2．利用BFS、DFS算法求解生成树问题和利用Kruskal算法求图G的最优树。 3．利用KM算法求解最佳匹配问题 4．利用奇偶点作业法求解中国邮路问题

练习题目：

1．利用Dijkstra算法，求解下图中从顶点1到其余各点的最短路径。

2．（1）分别用BFS和DFS算法寻找图G的一个生成树； （2）利用Kruskal算法求图G的最优树。

3．求出K5,5（对应权矩阵如下）的最佳匹配。

?3??2?2??0?1?

5541?

?

2022?4410?

?

1100?2133??

4．求出下图中的一条中国邮路，并给出求解过程。

本文来源：https://www.bwwdw.com/article/7by2.html