2. 计算机
  3. n个城市由k条公路网连接(一条公路定义为两个城市间的一条道路，它们之间不能通过任何中间城市)，证明：如果有 k＞l/2(n-1)(n-2) 则人们总能通过连接城市的公路在任何两个城市之间旅行。

n个城市由k条公路网连接(一条公路定义为两个城市间的一条道路，它们之间不能通过任何中间城市)，证明：如果有 k＞l/2(n-1)(n-2) 则人们总能通过连接城市的公路在任何两个城市之间旅行。

admin2009-07-15  25
问题 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全国计算机四级

相关试题推荐
随机试题
最新回复(0)