首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
自考
有29条边的无向连通图,至少有________个顶点,至多有________个顶点;有29条边的无向非连通图,至少有_________个顶点。有29条边(弧)的有向连通图,至少有_________个顶点,至多有_________个顶点;有29条边的有向非连
有29条边的无向连通图,至少有________个顶点,至多有________个顶点;有29条边的无向非连通图,至少有_________个顶点。有29条边(弧)的有向连通图,至少有_________个顶点,至多有_________个顶点;有29条边的有向非连
admin
2014-12-25
41
问题
有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
数据结构导论
理工类
相关试题推荐
某单位申请到一个B类IP地址,其网络号(NetID)为130.53,现进行子网划分,若选用的子网掩码为255.255.224.0,则最多可划分出多少个子网?每个子网中的最大主机数为多少?请列出全部子网的起始地址(假设路由协议支持全0和全1的子网)。
所谓______,其实就是提供了一种按层次结构组织的信息,然后按名称关联检索信息的服务方式。
细缆以太网的最大网络干线长度为【】
在E-R图中,椭圆框表示的是()
请根据以下调查结果绘制计划部分的数据流程图:根据定货合同提供的物资领用计划汇总编写成材料领用计划,再结合材料消耗定额本上的数据计算编写成限额发料文件,打印此文件,并交保管员保存。
ERP、MRP、MRPⅡ三者之间的关系是()
ER图是数据库设计工具之一,它适用于建立数据库的()
若某计算问题的执行情况如下图:请回答下列问题:请画出能提高处理器利用率的执行方案。
在χy平面内,以10cm/s的恒速由点(2,4)到点(16,10)的作直线运动,采样周期0.02s。试导出χ(t)和y(t)在这两点之间的直线插补公式。
立方体单级网络的顶点二进制码是010,不能连接下列哪个顶点上()
随机试题
临床上鸡内金可用于治疗下列哪些病证( )
脾俞穴的定位是
锅炉的设计疲劳寿命是根据特定的条件确定的,其设计寿命的分配,一般会规定()等条件。
人们对刺激物产生的知觉有()等几种层次的理解。
[2014]ABC会计师事务所承接甲公司2013年度财务报表审计业务,在对存货进行监盘过程中,发生如下事项:(1)注册会计师不打算信赖被审计单位有关存货的内部控制,于是不再了解管理层用以记录和控制存货盘点结果的指令和程序。要求:
儿童计划免疫中,通过接种卡介苗防治和控制肺结核。卡介苗对于接种的人来说属于()。
预循环,是一种更环保的生活方式,指通过避免购人会产生垃圾的家庭或商业物品来减少垃圾数量的行为。可循环的垃圾经过处理后可以发挥别的功效,可是处理这些可循环物质也是要消耗能源并产生垃圾的,所以更加环保的方式是尽量减少使用会产生垃圾的物品。根据上述定义,下列各项
根据宪法,我国的国家机构包括()。
明太祖大力推行屯田政策,屯田主要有_______和_______两种,还有商屯。
随着中国国际【C12】______的不断提高,世界各地逐步掀起了“学汉语热”。中国的文化正逐步为世界所【C13】______、所接受,中国的工农业产品正逐步跨入更多国家的国门。【C14】______,或者只知道一些被歪曲了的形象。但是今天的中国【C15】_
最新回复
(
0
)