离散数学结构试题集

3. 关联同一节点的两条边叫做（ ）。 A）环 B)回路 C)圈 D）邻接边

4. 含有平行边的任何一个图叫做（ ）。

A）欧拉图 B）汉米尔顿图 C）连通图 D）多重图

5. 在一个含有n个节点的图中，度数为奇数节点的个数必为（ ）个。 A）2 B）n-1 C）偶数 D）奇数

6. 在任何有向图中，所有节点的出度之和等于（ ）。

A)所有节点的入度之和 B）所有节点入度之和的2倍 C）所有节点入度之和的一半 D）没有必然联系

7. 在含有n个节点的完全图中，其边数为（ ）。 A)n B)n-1 C)n+1 D)(n-1)n/2

8. 在含有n个节点的图，它有（ ）个补图。 A)1 B)n C) (n-1)n/2 D)0

9. .如果两个图是同构的，那么下面那条是错误的.( )

A)节点数相等 B)边数相等 C)度数相同的节点数相等 D)连通的

10. 在具有n个节点的图中，如果两个节点之间有路，则必有一条路的长度（ ）。 A)至少为n B)至少为n-1 C)至多为n-1 D)n

11. 若图G只有一个连通分支，则G叫作（ ）。

A)连通图 B)强连通图 C）欧拉图 D）平面图

12. 含有m个节点的简单图，其边数不会多于（ ）。

A）1 B）m C)m-1 D)m(m-1)/2

13. 含有n个节点的图，至少生成（ ）棵生成树。 A)1 B)n C) (n-1)n/2 D)0

14. 连通图必然有（ ）。

A）欧拉路 B)汉米尔顿路 C)欧拉回路 D)通过各节点的路

15. 如果一个连通图有m个结点，则它的邻接矩阵的秩为（ ）

A)m B)m+1 C)m-1 D)不确定

三.判断题

1. 在任何图中，度数为偶数的节点必有奇数个。( )

2. 在任何有向图中，所有节点的入度之和等于所有节点的出度之和。（ ）

3. 每个图中，边数等于节点度数的两倍。（ ）

4. 连通图必有欧拉回路。（ ）

5. 有汉米尔顿路的图必有欧拉路。（ ）

6. 含有欧拉回路的图中每个节点的度数必为偶数。（ ）

7. 含有欧拉回路的图必有汉密尔顿路。（ ）

8. 一个图的边连通度一定大于等于其点连通度。（

四.计算题

1. 画出下图的完全补图。

2. 给一个含有5个节点的自补图。

3. 求下图中 1）从A到F所有通路。 2）从A到F的所有迹。

4. 求下图的邻接矩阵，并求出可达性矩阵。

）