图论中的定义
- 设G=<V,E>为任意无向图，顶点总和为|V|，边数总和为|E| ，若|E|=m，则所有顶点的度数和=2m
图论-->现实的理解
- 顶点-->人
- 边-->人与人握手
- 度-->一个人与其他人握手的次数
- |E|=m-->共m次握手
- 总定理-->n个人参与握手，若发生握手的总次数为m,则每个人的握手次数之和为2m
- 理解：
- 假设只有两个人，求总握手次数
- 一次握手 == 两个人的握手次数分别加一 == 2个握手次数 ==总握手次数
- so:总握手次数==2m
- ps:不一定每个人都要与其他人握手，总度数只与总边数有关
握手定理引理
-
一定有偶数个奇数度，或者没有奇数度：
- 因为总度数==2m 偶数
-
度数和<=n(n-1) :
- 假设每个顶点都和其他顶点相连，则总度数=n*(n-1) (ps:顶点数*每个顶点的度数)
-
一定两个度数相同的节点
证明：
- 设G是具有n个结点的简单图(n≥2) ，所以节点度有 0，1，2。。。(n-1)共n中可能
- 但节点0或(n-1)不能同时于一张图
(0代表没有节点相连，(n-1)代表跟剩下的节点都相连) - 所以n个节点只有(n-1)种度可能，必定有两个度数相同的节点
网友评论