计算机四级考试辅导：计算机离散数学习题七

 

7.1   下列各组数中，哪些能构成无向图的度数列？哪些能构成无向简单图的度数列？

（1）1，1，1，2，3

（2）2，2，2，2，2

（3）3，3，3，3

（4）1，2，3，4，5

（5）1，3，3，3

7.2   设有向简单图的度数列为2，2，3，3，入度列为0，0，2，3，试求D的出度列。

7.3   设D是4阶有向简单图，度数列为3，3，3，3，它的入度列（或出度列）能为1，1，1，1吗？

7.4  设 为一正整数列， 互不相同，问此序列能构成 阶无向简单图的度数列吗？为什么？

7.5   下面各无向图中有几个顶点？

（1）16条边，每个顶点，其余的都是3度顶点。

（2）21条边，3个4度顶点，其余的都是3度顶点。

（3）24条边，各顶点的度数是相同的。

7.6   35条边，每个顶点的度数至少为3的图最多有几个顶点？

7.7   设 阶无向简单图G中， ，问 应为多少？

7.8   一个 阶无向简单图G中， 为奇数，已知 中有 个奇度顶点，问G的补图 中有几个奇度顶点？

7.9   设D是 阶有向简单图， 是D的子图，已知 的边数 ，问D的边数 为多少？

7.10  画出 的所有非同构的子图，其中有几个是生成子图？生成子图有几个是连通图？

7.11  设G为n阶简单图（有向的或无向的）， 为 的补图，若 ，则称G为自补图， 的生成子图中有几个非同构的自补图？

7.12  画出3阶有向完全图所有非同构的子图，问其中有几个是生成子图？生成子图中有几个是自补图？

7.13  设 均为4阶无向简单图，它们均有两条边，它们能彼此非同构吗？为什么？

7.14  已知 阶无向图G中有 条边，各顶点的度数无为3，已知 ，问在同构意义下，G是唯一的吗？若G为简单图时，是否唯一？

7.15  在 的边上涂上红色或蓝色，证明对于任意一种随意的涂法，总在存红色 或蓝色 。

7.16  试寻找3个4阶有向简蝉 ，使得 为强连通图； 为单向连通图，但不是强连通的；而 为弱连通图，但不是单向连能通的，更不是强连通的。

7.17  设 和 分别为无向连通图G的点割集和边割集， 的连通分支个数一定为几？ 的连通分支数也是定数吗？

7.18  有向图D如图7.1所示，求D中长度为4的通路总数，并指出其中有多少条是回路？又有几条是 到 的通路？

 

 

 

 

 

题7.19—7.23的要求是从供选择的答案中选出应填入叙述中的□内的正确答案。

7.19  设 阶图G中有 条边，每个顶点的度不是 就是 ，若G中有 个 度顶点， 个 度顶点，则 为A。

供选择的答案

A：① ；② ；③ ；④ ；⑤ 。

7.20   如果一个简单图 （ 为G的补图），则称G是自补图。

（1）非同构的无向的4阶自补图有A个；

（2）非同构的无向的5阶自补图有B个。

供选择的答案

A，B：①0；②1；③2；④3。

7.21   在图7.2所示的6个图中，强连通图为A，单向连通图为B，图（3） 为C， 为D。

 

 

 

 

 

 

 

供选择的答案

A，B：①（1），（2），（3）；②（4），（5），（6）；③（1），（2），（4），（5），（6）；④（1），（5），（6）。

C，D：①1；②2；③3；④ ；⑤0。

7.22  给定有向带权图如图7.3所示。

图中b到a的最短路径的权为A；b到d最短路径的权为B，b到e最短路径的权为C；b到g最短路径的权为D。

供选择的答案

A，B，C，D：①4；②5；③6；④7；⑤8；⑥9；⑦10。

 

 

 

 

 

7.23  图7.4所示的图为PERT图。

（1） 的最早完成时间为A，完成时间为B，缓冲时间为C；

（2）关键路径为D。

供选择的答案

A，B，C：①0；②1；③2；④3；⑤4；⑥5；⑦6；⑧7；⑨9；⑩10。

D：① ；② ；③ ；④ 。