首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
n个城市由k条公路网连接(一条公路定义为两个城市间的一条道路,它们之间不能通过任何中间城市),证明:如果有 k>l/2(n-1)(n-2) 则人们总能通过连接城市的公路在任何两个城市之间旅行。
n个城市由k条公路网连接(一条公路定义为两个城市间的一条道路,它们之间不能通过任何中间城市),证明:如果有 k>l/2(n-1)(n-2) 则人们总能通过连接城市的公路在任何两个城市之间旅行。
admin
2009-07-15
31
问题
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系统中,将指针移向特定图表时,会看到该图表的名称或某个设置的状态。例如,执行________图表将显示计算机当前音量级别。
获取操作数速度最快的寻址方式是__________________。
以下关于TCP/IP协议和层次对应关系的表示,正确的是(26)________________。
在IE浏览器中,单击<input>标记的type属性值为(42)的按钮可以将form表单内的数据发送到服务器。
以下关于802.11标准CSMA/CA协议的叙述中,错误的是()。
Every valid character in a computer that uses even(71)must always have an even number of 1 bits.
Whenyouopenafileorrunaprograminacomputer,awindowappearsonthedesktopofyourcomputer.The(67)ofthewindowindi
某系统总线的一个总线周期包含3个时钟周期,每个总线周期中可以传送32位数据。若总线的时钟频率为33MHz,则总线带宽为(18)。
In C language,(75) are used to create variables and are grouped at the top of a gram block.
InClanguage,(69)areusedtocreatevariablesandaregroupedatthetopofaprogramblock.
随机试题
【】就是把产品生产和产品消费看作一个整体,把产品的设计、生产和售后服务看作一个整体过程。
骨折早期功能锻炼原则是
根据《房屋登记办法》,房屋登记的种类包括()。[2010年考试真题]
某高速公路桥跨越的河流为Ⅱ类水体,下列说法错误的有()。
由生产技术水平决定的生产资料和劳动力之间的量的比例,被称为()。
根据下列资料,回答问题。根据以上资料,下列说法正确的是()。
甲、乙于某晚到A厂行窃,盗的银板精铜10块,价值人民币300元。二人携赃物逃离A厂时,被该厂保安发现追赶。二人将保安打倒在地后逃离A厂。后二人将盗得的精铜打造成戒指冒充金戒指出售,获利5万余元。对甲、乙的行为应当如何处理?
假定下列语句都是程序运行后首次执行的输出语句,其中输出结果与另外3条语句不同的语句是
WhatisitthatmadeSteveJobsspecial?Whatcanwelearnfromthisonce-in-a-lifetimeentrepreneur?SteveJobswasavisi
A、Checkwiththeemploymentresourcecenteratschool.B、Sendherresumestoallthemostprominentaccountingfirms.C、Resortt
最新回复
(
0
)