V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
tesorouo
V2EX  ›  问与答

怎样证明一个网络结构中如果有 n 个节点,则每个节点至少要有 n/2 个链路才能使得所有节点被连结?

  •  
  •   tesorouo · 2020-04-07 10:00:18 +08:00 · 970 次点击
    这是一个创建于 1678 天前的主题,其中的信息可能已经有所发展或是发生改变。
    4 条回复    2020-04-08 09:33:37 +08:00
    kizunai
        1
    kizunai  
       2020-04-07 10:54:35 +08:00 via iPhone
    我感觉……每个节点至少有 1 个链路即可
    不妨令一个节点为父节点,其余 n-1 个节点只需要有一个链路链接到父节点就可以让所有节点被链接了。
    是我没有理解对题目吗?
    hahiru
        2
    hahiru  
       2020-04-07 10:57:17 +08:00   ❤️ 1
    欧拉把问题的实质归于一笔画问题,即判断一个图是否能够遍历完所有的边而没有重复,而柯尼斯堡七桥问题则是一笔画问题的一个具体情境。欧拉最后给出任意一种河──桥图能否全部走一次的判定法则,从而解决了“一笔画问题”。对于一个给定的连通图,如果存在超过两个(不包括两个)奇顶点,那么满足要求的路线便不存在了,且有 n 个奇顶点的图至少需要 n/2 笔画出。如果只有两个奇顶点,则可从其中任何一地出发完成一笔画。若所有点均为偶顶点,则从任何一点出发,所求的路线都能实现,他还说明了怎样快速找到所要求的路线。
    WorldHi
        3
    WorldHi  
       2020-04-08 09:05:37 +08:00 via iPhone
    @kizunai 应该是不允许设计线路,感觉证明方式跟抽屉原理相似吧 大于 n/2 保证了任意两个相连节点要么直连或者存在公共节点同时和这两个节点相连
    tesorouo
        4
    tesorouo  
    OP
       2020-04-08 09:33:37 +08:00
    @WorldHi 我觉着你应该在正确的路上,应该是通过 GPHP 证明的
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2662 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 23ms · UTC 11:04 · PVG 19:04 · LAX 03:04 · JFK 06:04
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.