首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
自考
有29条边的无向连通图,至少有________个顶点,至多有________个顶点;有29条边的无向非连通图,至少有_________个顶点。有29条边(弧)的有向连通图,至少有_________个顶点,至多有_________个顶点;有29条边的有向非连
有29条边的无向连通图,至少有________个顶点,至多有________个顶点;有29条边的无向非连通图,至少有_________个顶点。有29条边(弧)的有向连通图,至少有_________个顶点,至多有_________个顶点;有29条边的有向非连
admin
2014-12-25
69
问题
有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
数据结构导论
理工类
相关试题推荐
按拓扑结构来分类,计算机网络可分为总线形网络、_________、星形网络、树形网络、网状网络。
【】的主要功能是在传输介质上实现无结构比特流传输。
在网络协议的基本要素中,用来规定数据与控制信息的分组结构或格式的是【】
网络管理协议中的通信机制主要有两种,一种称为_______;一种称为事件报告。
在UML类图中,关联的端部,也就是与关联相连的类,称为________。
在对象联系图中,表示对象类型之间的超类与子类联系的是()
关系代数中基本操作是并、差、笛卡尔积、投影和选择,没有集合的________操作,因而关系代数运算总是安全的。
如图1.15所示,指出各顶点的度与奇偶性。
有3只球,4个盒子,盒子的编号为1、2、3、4,将球逐个独立地、随机地放人4只盒子中去,以X表示其中至少有一只球的盒子的最小号码,试求E(X).
随机试题
《饮冰室合集》是下面哪位历史人物的著作合集?()
人体内嘌呤核苷酸分解代谢的主要终产物是
依据施工验收规范,母线安装正确的排序是( )。
海运附加费中因港口不同情况而增收的附加费,包括港口附加费、港口拥挤费、选港费以及()。
甲公司2013年该公司分别销售A、B产品1万件和2万件,销售单价分别为100元和50元。甲公司向购买者承诺提供产品售后2年内免费负责保修服务,预计保修期内将发生的保修费在销售额的2%一8%之间(该区间内各金额发生的可能性相同)。2013年实际发生保修费1万
秋季运动会结束了,三班的同学比较沮丧,他们的成绩比原来差了很多,但是班主任和大家分析了原因以后,大家很快找到了症结,定下了下次一定要取得好成绩的目标,并做出了具体的计划,大家又精神抖擞起来。此时的班集体属于()。
Samuel:Hey,______?Diana:IwishIcould.ButIreallyhavetostayinandfinishmypapertonight.Samuel:Oh,maybesomeoth
结合材料回答问题。材料1“才者,德之资也;德者,才之帅也”。德与才,是辩证统一的两个方面,二者缺一不可。重才轻德,历来是用人的大忌。具备良好品德,才有忠于事业、为民服务的恒久动力;具备出色才干,才有胜任本职工作的专业技能。德才兼备,我们
下列叙述中,错误的是()。
Fromgoodreadingwecanderivepleasure,companionship,experience,andinstruction.Agoodbookmayabsorbourattentionsoco
最新回复
(
0
)