当前位置: 首页 > 问题分类 > 计算机类考试 > 计算机四级 > 问题详情
问题

n个城市由k条公路网连接(一条公路定义为两个城市间的一条道路,它们之间不能通过任何中间城市),证明:如果有

k>l/2(n-1)(n-2)

则人们总能通过连接城市的公路在任何两个城市之间旅行。

参考答案
正确答案:将城市作为结点将连接两个城市的公路作为边则该问题等价于证明一个具有n个结点k条边的简单无向图G是连通图。当n=2时结论显然成立以下证明n>2时结论也成立。 假设G不连通则可将G中的结点集V分为两个子集V1和V2它们.满足V1∪V2=VV1∩V2≠并且V1中的任何结点与V2中的任何结点均不连通。设由V1生成的G的子图G1中有n1个结点k1条边由V2生成的G的子图G2中有n2个结点k2条边则n1+n2=nk1+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不妨设n12.由②得 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是连通图。
将城市作为结点,将连接两个城市的公路作为边,则该问题等价于证明一个具有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,不妨设n12.由②得 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是连通图。
您可能感兴趣的试题
  • 与汇编程序相比,C语言程序的优点包括( )。

    A、更容易移植

    B、更容易阅读

    C、目标代码质量较高

    D、能够进行位操作

  • 多用户的数据库系( )

    A安全性控制

    B完整性控制

    C并发控制

    D可靠性控制

  • 下面关于联机分析处理OLAP,说法正确的是( )

    AOLAP系统工程跨越多个数据库模式,处理不同的信息和多个数据存

    BOLAP系统的访问主要由短的原子事务组成,需要并行控制和恢复机制

    C与OLTP相比,OLAP的视图是汇总的、统一的

    DOLAP通常采用实体-联系模型和面向应用的数据模式

  • 在关系模型中,数据的关系具有()

    A对称性

    B非对称性

    C抽象性

    D周期性