2. 自考
  3. 有29条边的无向连通图，至少有________个顶点，至多有________个顶点；有29条边的无向非连通图，至少有_________个顶点。有29条边(弧)的有向连通图，至少有_________个顶点，至多有_________个顶点；有29条边的有向非连

有29条边的无向连通图，至少有________个顶点，至多有________个顶点；有29条边的无向非连通图，至少有_________个顶点。有29条边(弧)的有向连通图，至少有_________个顶点，至多有_________个顶点；有29条边的有向非连

admin2014-12-25  25
问题 有29条边的无向连通图，至少有________个顶点，至多有________个顶点；有29条边的无向非连通图，至少有_________个顶点。有29条边(弧)的有向连通图，至少有_________个顶点，至多有_________个顶点；有29条边的有向非连通图，至少有_________个顶点。
选项
答案9 30 10 6 29 7
解析 对于n个顶点的无向连通图G，为完全图时边数达到最多：共n(n一1)／2条边，满足不等式n(n一1)／2≤29最大的n为8，即8个顶点的连通无向图最多28条边，因此有29条边的连通无向图至少有9个顶点；当G为树时边数达到最少：：共n一1条边，因此有29条边的连通图中至多30个顶点。因为29条边9个顶点的无向图必定是连通的，29条边的非连通无向图至少有10个顶点(一个子图为含8个顶点的完全图，另一个子图为含两个顶点的完全图)。因为5个顶点的有向完全图最多20条边，6个顶点的有向完全图最多30个结点。因此有29条弧的有向连通图至少有6个顶点，至多29个顶点。29条边6个顶点的有向图必定是连通的，要不连通至少有7个顶点。
转载请注明原文地址:https://kaotiyun.com/show/o4Vx777K
本试题收录于： 数据结构导论题库理工类分类
0

数据结构导论

理工类

相关试题推荐
随机试题
最新回复(0)