发布时间 : 星期一 文章离散数学结构试题集更新完毕开始阅读99a8e542e45c3b3567ec8bca
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. 求下图的邻接矩阵，并求出可达性矩阵。
）