正则图怎么判断：顶点度数、环形例子与边数计算

热点话题

正则图最直接的判断标准，是每个顶点连接的边数是否相同。在有限、无向、没有自环和重边的简单图中，如果每个顶点的度都是k，这个图就是k正则图。图画得是否对称、顶点排得是否整齐，都不是定义条件。

从三个小例子入手

一组互不相连的点，每点度数为0，是0正则图。若顶点两两配对，每点只接一条边，就是1正则图。把若干顶点依次连成一个环，每点都接前后两个邻点，便得到2正则图。即使画图时把其中某个点拉远，只要连接关系不变，正则性也不会改变。

为什么边数是nk除以2

设图有n个顶点，每点度数为k，所有度数相加得到nk。每条无向边在两个端点各被数一次，所以实际边数是nk/2。例如6个顶点组成的环，每点度数为2，边数就是6。若计算得到半条边，说明给定的n与k至少不满足必要的奇偶条件。

正则图不一定是完全图

完全图要求任意两个不同顶点都有边，而正则图只要求所有点的度相等。六个点组成的环是正则图，却有许多点对没有直接相连。做题时先逐点数度，再检查是否存在全部可能的边，便能把“正则”与“完全”两个概念清楚分开。

资料依据：维基百科《正則圖》及该页贡献者（修订记录）。本篇重新编排论述、改写表达并补充阅读解释；依Creative Commons Attribution-Share Alike 4.0提供。