首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
n个城市由k条公路网连接(一条公路定义为两个城市间的一条道路,它们之间不能通过任何中间城市),证明:如果有 k>l/2(n-1)(n-2) 则人们总能通过连接城市的公路在任何两个城市之间旅行。
n个城市由k条公路网连接(一条公路定义为两个城市间的一条道路,它们之间不能通过任何中间城市),证明:如果有 k>l/2(n-1)(n-2) 则人们总能通过连接城市的公路在任何两个城市之间旅行。
admin
2009-07-15
33
问题
n个城市由k条公路网连接(一条公路定义为两个城市间的一条道路,它们之间不能通过任何中间城市),证明:如果有
k>l/2(n-1)(n-2)
则人们总能通过连接城市的公路在任何两个城市之间旅行。
选项
答案
将城市作为结点,将连接两个城市的公路作为边,则该问题等价于证明一个具有n个结点k条边的简单无向图G是连通图。当n=2时,结论显然成立,以下证明n>2时结论也成立。 假设G不连通,则可将G中的结点集V分为两个子集V1和V2,它们.满足V1∪V2=V,V1∩V2≠[*],并且V1中的任何结点与V2中的任何结点均不连通。设由V1生成的G的子图G1中有n1个结点k1条边,由V2生成的G的子图G2中有n2个结点k2条边,则n1+n2=n,k1+k2=k。由于G是简单无向图,因此G1和G2也是简单无向图,从而有 k1≤1/2 n1(n1-1),k2≤1/2 n2(n2-1) 于是 k=k1+k2≤1/2 n1(n1-1)+1/2 n2(n2-1) ① 又 k>1/2(n-1)(n-2)=1/2(n1+n2-1)(n1+n2-2) ② 由于n>2,因此n1和n2至少有一个大于等于2,不妨设n1≥2.由②得 k>1/2(n1+n2-1)(n1+n2-2)=1/2 n1(n1+n2-2)+1/2(n2-1)(n1+n2-2)≥1/2 n1(n1-1)+1/2 n2(n2-1) 这与①式矛盾,故G是连通图。
解析
转载请注明原文地址:https://kaotiyun.com/show/kxNZ777K
0
笔试
原NCRE全国计算机四级
NCRE全国计算机四级
相关试题推荐
可在Windows“运行”窗口中键入(68)命令来运行Microsoft管理控制台。
程序运行过程中,把函数(或过程)调用与响应调用所需要的代码相结合的过程称为______。
按照《计算机软件保护条例》的规定,自然人的软件著作权的保护期限为(25)。
Windows系统中的磁盘碎片整理程序______。
Internet涉及许多协议,下面的选项中能正确表示协议层次关系的是__________________。
阅读以下应用说明及VisualBasic部分程序代码,将应填入(n)处的字句写在对应栏内。【说明】本应用程序是一个小写数字转换成大写格式的转换器,其运行窗口如图5所示。窗口中有两个标签(lblNumber和lblChinese)、
某系统总线的一个总线周期包含3个时钟周期,每个总线周期中可以传送32位数据。若总线的时钟频率为33MHz,则总线带宽为(18)。
在下列程序中:Programtest(input,output);vari.j:integer;procedurecalc(p1,p2:integer);beginp2:=p2*p2p1:=p1
What is the decimal value of tile binary value 100107(70).
随机试题
夏季某餐厅供应蛋炒饭引起近百人食物中毒,发病者潜伏期约8小时,以腹痛、腹泻为主要症状,体温正常,经16~36小时全部恢复。经卫生学调查发现蛋炒饭使用的是前一天的剩饭为预防这种食物中毒的发生,剩余食物食前须彻底加热,一般应为
根据《企业国有资产法》的规定,履行出资人职责的机构有权任免的人员是()。
在Word中,对于选中的文字能够实现“复制”功能的操作有( )。
下列房屋附属设备和配套设施,无论在会计核算中是否单独记账与核算,都应计入房产原值,计征房产税的有()。
运动符号办事的能力是()。
下列做法符合可持续发展战略的有()。
下面是有关DRAM和SRAM存储器芯片的叙述:I.DRAM芯片的集成度比SRAM高Ⅱ.DRAM芯片的成本比SRAM高Ⅲ.DRAM芯片的速度比SRAM快Ⅳ.DRAM芯片工作时需要刷新,SRAM芯片工作时不需要刷新通常情况下,错误的是()。
波表(wave table)就是波形表,下列有关它的叙述正确的是( )。
计算机的硬件系统主要包括:中央处理器(CPU)、存储器、输出设备和___________。
A、Shewasavolunteer.B、Shequittedherjob.C、Shehadapart-timejob.D、Shewasachurchgoer.A男士询问女士是否有做志愿者的经历,女士说有,那是十年前,她在
最新回复
(
0
)