图论复习题

（二）图论复习题

一、选择题

1．设图G＝，v?V，则下列结论成立的是 ( C ) ． A．deg(v)=2?E? B． deg(v)=?E? C．?deg(v)?2E [PPT 23] D．?deg(v)?E

v?Vv?V定理1 图G=（V，E）中，所有点的次之和为边数的两倍 2．设无向图G的邻接矩阵为

?0?1??1??0??01100?0011??0000??1001?1010??

则G的边数为( B )．

A．6 B．5 C．4 D．3

3、 设完全图Kn有n个结点(n?2)，m条边，当（ C）时，Kn中存在

欧拉回路．

A．m为奇数 B．n为偶数 C．n为奇数 D．m为偶数

解释：Kn每个结点的度都为n－1，所以若存在欧拉回路则n－1必为偶数。n必为奇数。

4．欧拉回路是（ B ）

A. 路径 B. 简单回路[PPT 40] C. 既是基本回路也是简单回路 D.既非基本回路也非简单回路

5．哈密尔顿回路是（ C ）

A. 路径 B. 简单回路 C. 既是基本回路也是简单回路 D.既非基本回路也非简单回路

[PPT 40]：哈密尔顿回路要求走遍所有的点，即是基本回路的点不重复，也可以

是简单回路的边不重复。

6．设G是简单有向图，可达矩阵P(G)刻划下列关系中的是（ C ） A、点与边 B、边与点 C、点与点 D、边与边

7．下列哪一种图不一定是树（C）。

A.无简单回路的连通图 B. 有n个顶点n-1条边的连通图 C. 每对顶点间都有通路的图 D. 连通但删去一条边便不连通的图

8．在有n个结点的连通图中，其边数（B）

A.最多有n-1条 B.至少有n-1条 C.最多有n条 D.至少有n条

9．下列图为树的是（C）。

A、G1??{a,b,c,d},{?a,a?,?a,b?,?c,d?}? B、G2??{a,b,c,d},{?a,b?,?b,d?,?c,d?}? C、G3??{a,b,c,d},{?a,b?,?a,d?,?c,a?}? D、G4??{a,b,c,d},{?a,b?,?a,c?,?d,d?}? 10、下面的图7-22是（C）。

A.完全图；B.平面图；C.哈密顿图；D. 欧拉图。

二、填空题

1．无向完全图K6有 15 条边。[6×（6-1）]/2=15 2．设连通无向图G有k个奇顶点，要使G变成欧拉图，在G中至少要 加 k/2 条边。

解：∵任何图中的奇点的个数为偶数

∴在每对奇点处多加一条边形成了多重边，G图就成了欧拉图。 ∵连通无向图G有k个奇顶点 ∴有k/2对奇顶点

∴有多少对奇点就加多少条边 3、n阶无向完全图Kn

n(n-1)的边数是(

2)，每个结点的度数是(n-1)。

证明：∵1个顶点的图有0条边

2个顶点的图有1条边

∴满足1?2?（2?1） 2当3个顶点以上时 假如n=k-1 k>=3时

(k?1)(k?2)k23k???1条边 ∵k-1个顶点的图有

222k(k?1)k2k??条边 k个顶点的图有

222∴k-1个顶点的图与k个顶点的图产生的边数为

k23kk2k(??1)?(?)?k?1 2222而又∵k-1

个顶点的图的边数加上这条边k-1恰好为

k23kk(k?1)(??1)?(k?1)? 222∴当n=k时满足条件

∴一个具有N个顶点的无向完全图的边数为

n(n-1) 24、n个结点的有向完全图边数是( n(n-1) )，每个结点的度数是( 2n-2 )。

解：仿用握手定理

假设把每个顶点看成一个人

A点到B点相当于A主动向B伸手。 每个点要与n-1个点握手。

因为是有向的，所以A向B伸手和B向A伸手有区别。 总共握手次数是n(n-1) 所以总共边数是n(n-1)

?0?15、设有向图G = < V，E >，V?{v1,v2,v3,v4}的邻接矩阵A???1??1?101001001??1?， ?0?0??则v1的入度deg?(v1)= 3 ，v4的出度deg?(v4)= 1 ，

6、一棵无向树的顶点数为n，则其边数为 n-1 ，其结点度数之和是 2(n-1) 。所有的次之和为边数的两倍

7、一个无向图有生成树的充分必要条件是(此图为连通图)。

8、设T=〈V,E〉是一棵树，若|V|>1，则T中至少存在( 2 )片树叶。 9、任何连通无向图G至少有( 1 )棵生成树，当且仅当G 是( 树 )，G的生成树只有一棵。

10、设T是一棵树，则T是一个连通且(无圈)的图。

11、设无向图G有18条边且每个顶点的度数都是3，则图G有( 12 )个顶点。

解：∵18条边的次之和为?d(v)?2E?36，

v?V且每个顶点的度数都是3 ∴顶点数为36/3=12。 如图：

12、任一有向图中，度数为奇数的结点有( 偶数 )个。[PPT 23] 13、一棵树有2个2度顶点，1 个3度顶点，3个4度顶点，则其1度顶点为（ 9 ）。如图：

14、设G是由5个顶点组成的完全图，则从G中删去（ 6 ）条边可以得到树。

解： ∵5个顶点组成的完全图边数为又∵树有5个顶点

5?（5-1）?10 2∴树的边数应为4

∴完全图应删除10-4=6条边可以得到树。

15、已知图G是相邻矩阵为 则G的边数为（ B ）。 A.5； B.4； C.6

0

? ? 0 ? 1 ? ? 0 ? 0 ?? 0 0 0 1 1

1 0 0 0 0

0 1 0 0 1

0

? 1 ? 0 ?? 1 ? ? 0 ? ?

三、计算题

1．设G=，V={ v1，v2，v3，v4，v5}，E={ (v1,v3)，(v2,v3)，(v2,v4)，(v3,v4)，(v3,v5)，(v4,v5) }，试

(1) 给出G的图形表示； (2) 写出其邻接矩阵； (3) 求出每个结点的度数；

解：(1) (2)

G?(gij)5?5?0?0???1??0??00100?0110??1011??

1101?0110??(3)、每个结点的度数分别为

本文来源：https://www.bwwdw.com/article/6fso.html