![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/d/d6/UndirectedDegrees_%2528Loop%2529.svg/langzh-sg-640px-UndirectedDegrees_%2528Loop%2529.svg.png&w=640&q=50)
度 (图论)
在图论中,一个顶点在图中的度 (degree)为与这个顶点相连接的边的数目 / 维基百科,自由的 encyclopedia
在图论中,一个顶点在图中的度 (degree)为与这个顶点相连接的边的数目。在多重图中,自环被计数两次。[1] 顶点 的度记作
或
。图G的最大度记作Δ(G),最小度记作δ(G),分别为图中所有顶点度的最大值和最小值。 在右边的多重图中,最大度为5,最小度为0。 在正则图中,所有度都是相同的,因为我们可以直接说该图的度是多少。 完全图是正则图中的一种特殊情况,其任意两个点均相连,若顶点数为p,则该图的度为p-1。
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/thumb/d/d6/UndirectedDegrees_%28Loop%29.svg/220px-UndirectedDegrees_%28Loop%29.svg.png)
给定一个图,其度求和公式为:
该公式表明,在任意无向图中,度为奇数的顶点的个数为偶数,即为握手定理。该定理名称来自于一个热门的数学问题,即证明在一个团体中与他人握手奇数次的人的数量为偶数个。
对于有向图:
- 节点(顶点)的入度是指进入该节点(顶点)的边的条数;
- 节点(顶点)的出度是指从该节点(顶点)出发的边的条数。