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

admin2014-12-25 70

问题有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://www.kaotiyun.com/show/o4Vx777K

本试题收录于：数据结构导论题库理工类分类

数据结构导论

理工类

相关试题推荐

随机试题

最新回复(0)

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

数据结构导论

理工类

实现数字签名的方法分为对称密钥签名和_____两种。

恶意程序造成的破坏有哪些?

操作系统的【】是指在多道程序环境下，由于资源的竞争或共享，程序的执行会走走停停，因此多个程序的执行顺序及所需的执行时间将变得不可预知。

甘特图是一个二维平面图，其中横向维表示__或活动的时间，纵向维表示工作的_。

数据库系统生存期中，下面不是需求分析阶段工作的是()

集成运放应用电路中，若引入深度负反馈，则运放工作在______区。

下列矩阵中，不是概率矩阵的是()

对如图所示的网，求任意两个顶点之间的最短路径。