You need to enable JavaScript to run this app.
最新活动
大模型
产品
解决方案
定价
生态与合作
支持与服务
开发者
了解我们

求证:任意有限图的所有顶点度数之和为偶数

证明:任意有限图的所有顶点度数之和为偶数

这是图论里非常基础且经典的结论,咱们顺着思路一步步把证明理清楚:

  1. 初始状态分析
    先从空图开始——也就是只有顶点、没有任何边的状态。这时候所有顶点的度数都是0,整个图的度数总和为0,0是偶数,符合我们要证明的奇偶性前提。

  2. 逐条添加边的过程分析
    我们逐个往图里添加边,不管添加哪种类型的边,都只会让度数总和增加偶数:

    • 若添加的是连接两个不同顶点的边:这条边会让这两个顶点的度数各+1,总和总共增加2(1+1)。偶数加偶数还是偶数,所以总和的奇偶性保持不变,依然是偶数。
    • 若允许添加自环(连接单个顶点的边):根据图论的度数定义,自环会让该顶点的度数+2(自环在度数计算中算2度),总和同样增加2,奇偶性还是保持偶数不变。

不管我们给这个有限图添加多少条边,每一步操作都不会改变度数总和的奇偶性。初始总和是偶数,所以最终任意有限图的顶点度数之和必然是偶数。

内容的提问来源于stack exchange,提问作者user532588

火山引擎 最新活动