什么是度，什么是握手定理 | 集智百科

“集智百科精选”是一个长期专栏，持续为大家推送复杂性科学相关的基本概念和资源信息。作为集智俱乐部的开源科学项目，集智百科希望打造复杂性科学领域最全面的百科全书，欢迎对复杂性科学感兴趣、热爱知识整理和分享的朋友加入！

本文是对集智百科中“度”词条的摘录，参考资料及相关词条请参阅百科词条原文。

本词条由集智俱乐部众包生产，难免存在纰漏和问题，欢迎大家留言反馈或者前往对应的百科词条页面进行修改，一经修改，可以获得对应的积分奖励噢！

目录

一、什么是度？

二、握手定理

三、度序列

四、特殊值

五、全局模型

六、相关资源推荐

七、集智百科词条志愿者招募

度： https://wiki.swarma.org/index.php?title=度_Degree

1. 什么是度？

在图论 Graph theory中，图中顶点的 度 Degree (或价)是入射到该顶点的边的数量。在 多重图 Multigraph 中， 自环 Loops 会被计算两次。顶点的度数可表示为 或 。一个图 的最大度值可表示为 ，最小度值可表示为 。在右侧的多重图中，最大度值为5，最小度值为0。

在 正则图 Regular Graph 中，每个顶点都具有相同的度数，因此我们可以将其称之为该图的度数。一个 完全图 Complete Graph （表示为 ，其中 是图中顶点的数目）是一种特殊的正则图，它所有顶点都有最大度值， 。

图1：内含自环按度标记的图

2. 握手定理

度和公式 Degree Sum Formula 表明，任意给定一个图 ,都有

:

此公式表明，在任何无向图中，拥有奇数度值的顶点的个数是偶数。这一阐释（以及度和公式）被称为握手引理 Handshaking Lemma。该名称来自一个有趣的数学问题，即求证无论该群体内有多少人，与奇数个人握过手的人数总是偶数。

3. 度序列

无向图的度序列是指将其各顶点度值按非递增方式排序，对于上述图是（5，3，3，2，2，1，0）。度序列是图不变量 Graph Invariant，因此同构图 Non-isomorphic Graphs（两个图中顶点的度值都相同，但形状不同）具有相同的度序列。然而，度序列通常不能唯一地标识一个图，在某些情况下，非同构图也会具有相同的度序列。

图2：同一度序列（3，2，2，2，2，1，1，1）的非同构图

度序列问题 Degree Sequence Problem，是指寻找度序列为给定的非递增正整数序列的局部或全部图的问题。（序列尾部的零可能会被忽略，因为通过向图中添加适当数量的孤立顶点就可以轻松实现序列尾部不断加零。）一个序列是某个图的度序列，即一个度序列问题有解时，该序列称为图形序列。由于度和公式的存在，任何具有奇数和的序列，如（3，3，1） ，都不会是图的度序列。反之亦然：如果一个序列和是偶数，它就是重图的度序列。我们可以轻易地构造一个图：匹配奇数度值的顶点并成对连接起来，然后剩余的偶数度值顶点都连出一条边指向图形/起点本身。

“一个给定的度序列是否可以用一个简单的图进行表示”是一个具有挑战性的问题。这个问题也称为这个问题也称为图实现问题 Graph Realization Problem，但它可以用Erdős–Gallai定理 Erdős–Gallai Theoreme解决，也可以用Havel-Hakimi算法 Havel–Hakimi Algorithm解决。

基于给定度序列寻找或估计可能的图的个数，是图枚举 Graph Enumeration领域中的一个问题。

一般来说， 超图 Hypergraph 的度序列是其顶点度的非递增序列。如果一个序列是 -一致超图 k-uniform hypergraph 的度序列，那么它即是 -graphic。特别地， -graphic序列是图形。决定一个给定的序列是否是 -graphic可以在 的多项式时间内通过 Erdős–Gallai定理 Erdős–Gallai Theoreme 实现，但是当 时该问题可转化为 NP完全问题。

4. 特殊值

• 度数为0的顶点称为孤立顶点 Isolated Vertex

• 度数为1的顶点称为叶顶点或尾顶点，该顶点的入射边称为悬挂边 Pendant Edge。在右侧的图中，{3,5}就是一个悬挂边。在图论中，该术语主要在研究树 Tree时使用，特别是具有树形结构的数据。

• 在有n个顶点的图中，度数为n-1的顶点叫作主导顶点 Dominating Vertex

图3：一个具有叶节点的无定向图

5. 全局模型

• 如果一个图中的所有顶点的度值都为k，那么该图被称为k-正则图 k-regular graph，该图的度数也为k。同样的，同侧每两个顶点都具有相同度数的二分图叫作二分正则图 Biregular Graph。

• 当且仅当一个图具有0或2个奇数度的顶点时，无向连通图才具有欧拉路径 Eulerian Path。如果它具有0个奇数度的顶点，则欧拉路径为欧拉回路 Eulerian Circuit。

• 当且仅当每个顶点的出数最大值为1时称该图为有向图伪森林 Pseudoforest。功能图 Functional Graph是伪森林的特例，其中每个顶点的出度都恰好为1。

• 根据布鲁克斯定理，除团簇或奇数循环外，任何图的色数 chromatic number 最大为Δ，而根据维辛定理 Vizing's theorem，任何图的色指数chromatic index 最大为Δ+ 1。

• k -退化图 K-Degenerate Graph是指图中每个子图都有一个顶点度数不大于k的图。

6. 相关资源推荐

课程推荐

本课程中，我们有幸邀请了汪小帆、赵海兴、许小可、史定华、陈清华、张江、狄增如、陈关荣、樊瑛、刘宗华这十个来自六大不同高校、在网络科学领域耕耘许久的教授作为导师，依据教材框架，各有侧重地为我们共同勾勒出整个学科的美丽图景，展示这个学科的迷人魅力，指引这个学科的灿烂未来。

我们将颠覆传统老师通篇主讲的课堂模式，用一种前所未有的集智课堂形式来解惑答疑，帮助大家完成从散点思维到网络思维，直至网络科学思维的跃升。

课程推荐：巴拉巴西网络科学 https://campus.swarma.org/course/1754

积分充值活动

集智的课程视频关注复杂系统和人工智能等跨学科前沿领域，在复杂系统建模、图神经网络、网络科学、计算社会科学、因果科学等领域有大量全网独家内容。

我们特推出积分充值活动，本次活动持续至2月11日。积分可以用于购买集智学园站内课程、参与集智俱乐部读书会。现在充值集智学园积分（∫），可获赠额外积分和复杂性科学知识卡片。

扫码充值

积分充值规则：

充值 500 元，得 55000 ∫，赠送 4 副限量版复杂性科学知识卡

充值 1000 元，得 110000 ∫，赠送 10 副限量版复杂性科学知识卡

复杂性科学知识卡（扑克）2.0版

7. 百科项目志愿者招募

作为集智百科项目团队的成员，本文内容由Ryan参与贡献。我们也为每位作者和志愿者准备了专属简介和个人集智百科主页，更多信息可以访问其集智百科个人主页。

以上内容都是我们做这项目的起点，作为来自不同学科和领域的志愿者，我们建立起一个有效的百科团队，分配有审校、翻译、编辑、宣传等工作。我们秉持：知识从我而来，问题到我为止的信念，认真负责编撰每一个词条。

在这里从复杂性知识出发与伙伴同行，同时我们希望有更多志愿者加入这个团队，使百科词条内容得到扩充，并为每位志愿者提供相应奖励与资源，建立个人主页与贡献记录，使其能够继续探索复杂世界。

集智百科报名表

来源：集智百科 编辑：曾祥轩