图论（一）度序列与Havel-Hakimi定理

古城微笑少年丶 2022-04-08 15:49 146阅读 0赞

我一直想写一些关于图论学习的收获。一直由于这样或者那样的原因都没有开始。无论如何，现在开始吧！

那么到底什么是图呢？我们这里说的图当然不是像照片一样的东东。最权威的定义：图=顶点集合+边集合。换言之，凡是能抽象成点集合和边集合的东西都是图。比如：中国地图。地图上的城市是一个个的点，而任意两个相邻城市之间有路。那么地图就是很直观的一种图。为了更方便的表示，我们引入了英语单词。Vertext(顶点),Edge(边)，Graph（图）。不管什么图，就可以用G<V,E>表示了。

地图是一种图，中国的七大水系网也是一种图。很多湖泊可以视为点，而长江、黄河这些可以看作边。由于水流基本上是单向的(当然也有倒流的情况，这里我们理想化就忽略了)，所以，像这样：边有方向的图我们称为有方向的图（长江水只能从喜马拉雅流向东海，而绝对不会反过来的）简称有向图。如果边没有方向，那当然称为无向图了。

我们还是回到地图。都说条条大路通北京（你说罗马也没错），那么有到底有多少条路到北京呢？在图论里，把这样连接到一个点的边的数量（比如连接到北京的路）称为：度！

对于图的所有顶点，我们可以统计出每个顶点的度。像这样的一串数字，我们称之为：度序列。那么反过来，给定一个序列，能否判断这个序列是可图的呢？这里有一个定理：Havel-Hakimi定理可以用来判定一个序列是否可图。Poj1659就是用Havel-Hakimi解决的。

Havel-Hakimi定理的内容可百度之。

Havel-Hakimi定理很容易理解：

三步走就可以了：

比如序列：4 7 7 3 3 3 2 1

<table> 
 <tbody> 
  <tr> 
   <td> 
    <div>
      下标 
    </div> </td> 
   <td> 
    <div>
      1 
    </div> </td> 
   <td> 
    <div>
      2 
    </div> </td> 
   <td> 
    <div>
      3 
    </div> </td> 
   <td> 
    <div>
      4 
    </div> </td> 
   <td> 
    <div>
      5 
    </div> </td> 
   <td> 
    <div>
      6 
    </div> </td> 
   <td> 
    <div>
      7 
    </div> </td> 
   <td> 
    <div>
      8 
    </div> </td> 
  </tr> 
  <tr> 
   <td> 
    <div>
      值 
    </div> </td> 
   <td> 
    <div>
      4 
    </div> </td> 
   <td> 
    <div>
      7 
    </div> </td> 
   <td> 
    <div>
      7 
    </div> </td> 
   <td> 
    <div>
      3 
    </div> </td> 
   <td> 
    <div>
      3 
    </div> </td> 
   <td> 
    <div>
      3 
    </div> </td> 
   <td> 
    <div>
      2 
    </div> </td> 
   <td> 
    <div>
      1 
    </div> </td> 
  </tr> 
 </tbody> 
</table>

第一步：把序列按降序排序。

<table> 
 <tbody> 
  <tr> 
   <td> 
    <div>
      下标 
    </div> </td> 
   <td> 
    <div>
      1 
    </div> </td> 
   <td> 
    <div>
      2 
    </div> </td> 
   <td> 
    <div>
      3 
    </div> </td> 
   <td> 
    <div>
      4 
    </div> </td> 
   <td> 
    <div>
      5 
    </div> </td> 
   <td> 
    <div>
      6 
    </div> </td> 
   <td> 
    <div>
      7 
    </div> </td> 
   <td> 
    <div>
      8 
    </div> </td> 
  </tr> 
  <tr> 
   <td> 
    <div>
      值 
    </div> </td> 
   <td> 
    <div>
      7 
    </div> </td> 
   <td> 
    <div>
      7 
    </div> </td> 
   <td> 
    <div>
      4 
    </div> </td> 
   <td> 
    <div>
      3 
    </div> </td> 
   <td> 
    <div>
      3 
    </div> </td> 
   <td> 
    <div>
      3 
    </div> </td> 
   <td> 
    <div>
      2 
    </div> </td> 
   <td> 
    <div>
      1 
    </div> </td> 
  </tr> 
 </tbody> 
</table>

第二步：删除第一个数7。序列变成

<table> 
 <tbody> 
  <tr> 
   <td> 
    <div>
      下标 
    </div> </td> 
   <td> 
    <div>
      1 
    </div> </td> 
   <td> 
    <div>
      2 
    </div> </td> 
   <td> 
    <div>
      3 
    </div> </td> 
   <td> 
    <div>
      4 
    </div> </td> 
   <td> 
    <div>
      5 
    </div> </td> 
   <td> 
    <div>
      6 
    </div> </td> 
   <td> 
    <div>
      7 
    </div> </td> 
  </tr> 
  <tr> 
   <td> 
    <div>
      值 
    </div> </td> 
   <td> 
    <div>
      7 
    </div> </td> 
   <td> 
    <div>
      4 
    </div> </td> 
   <td> 
    <div>
      3 
    </div> </td> 
   <td> 
    <div>
      3 
    </div> </td> 
   <td> 
    <div>
      3 
    </div> </td> 
   <td> 
    <div>
      2 
    </div> </td> 
   <td> 
    <div>
      1 
    </div> </td> 
  </tr> 
 </tbody> 
</table>

第三步：从头开始，数7个数，也就是下标：\[1,7\]把\[1,7\]区间里的值都减1

由于第一个数已经删除，那么序列变成这样的了：

<table> 
 <tbody> 
  <tr> 
   <td> 
    <div>
      下标 
    </div> </td> 
   <td> 
    <div>
      1 
    </div> </td> 
   <td> 
    <div>
      2 
    </div> </td> 
   <td> 
    <div>
      3 
    </div> </td> 
   <td> 
    <div>
      4 
    </div> </td> 
   <td> 
    <div>
      5 
    </div> </td> 
   <td> 
    <div>
      6 
    </div> </td> 
   <td> 
    <div>
      7 
    </div> </td> 
  </tr> 
  <tr> 
   <td> 
    <div>
      值 
    </div> </td> 
   <td> 
    <div>
      6 
    </div> </td> 
   <td> 
    <div>
      3 
    </div> </td> 
   <td> 
    <div>
      2 
    </div> </td> 
   <td> 
    <div>
      2 
    </div> </td> 
   <td> 
    <div>
      2 
    </div> </td> 
   <td> 
    <div>
      1 
    </div> </td> 
   <td> 
    <div>
      0 
    </div> </td> 
  </tr> 
 </tbody> 
</table>

然后：

重复第一步：排序。

重复第二步：删除第一个数6

重复第三步：从头开始数6个数：也就是下标【1,6】，把区间【1，6】中的数删除。序列变成：

<table> 
 <tbody> 
  <tr> 
   <td> 
    <div>
      下标 
    </div> </td> 
   <td> 
    <div>
      1 
    </div> </td> 
   <td> 
    <div>
      2 
    </div> </td> 
   <td> 
    <div>
      3 
    </div> </td> 
   <td> 
    <div>
      4 
    </div> </td> 
   <td> 
    <div>
      5 
    </div> </td> 
   <td> 
    <div>
      6 
    </div> </td> 
  </tr> 
  <tr> 
   <td> 
    <div>
      值 
    </div> </td> 
   <td> 
    <div>
      2 
    </div> </td> 
   <td> 
    <div>
      1 
    </div> </td> 
   <td> 
    <div>
      1 
    </div> </td> 
   <td> 
    <div>
      1 
    </div> </td> 
   <td> 
    <div>
      0 
    </div> </td> 
   <td> 
    <div>
      -1 
    </div> </td> 
  </tr> 
 </tbody> 
</table>

由于已经出现了-1，而一个点的边数（度）不可能为负数。所以，我们就可以判定序列无法构成一个图，所以此序列是不可图的。

下面再举一个例子：

已经排序：

<table> 
 <tbody> 
  <tr> 
   <td> 
    <div>
      5 
    </div> </td> 
   <td> 
    <div>
      4 
    </div> </td> 
   <td> 
    <div>
      3 
    </div> </td> 
   <td> 
    <div>
      3 
    </div> </td> 
   <td> 
    <div>
      2 
    </div> </td> 
   <td> 
    <div>
      2 
    </div> </td> 
   <td> 
    <div>
      2 
    </div> </td> 
   <td> 
    <div>
      1 
    </div> </td> 
   <td> 
    <div>
      1 
    </div> </td> 
   <td> 
    <div>
      1. 
    </div> </td> 
  </tr> 
 </tbody> 
</table>

删除第一个数5：

<table> 
 <tbody> 
  <tr> 
   <td> 
    <div>
      4 
    </div> </td> 
   <td> 
    <div>
      3 
    </div> </td> 
   <td> 
    <div>
      3 
    </div> </td> 
   <td> 
    <div>
      2 
    </div> </td> 
   <td> 
    <div>
      2 
    </div> </td> 
   <td> 
    <div>
      2 
    </div> </td> 
   <td> 
    <div>
      1 
    </div> </td> 
   <td> 
    <div>
      1 
    </div> </td> 
   <td> 
    <div>
      1. 
    </div> </td> 
  </tr> 
 </tbody> 
</table>

把前面5个数减1：

<table> 
 <tbody> 
  <tr> 
   <td> 
    <div>
      3 
    </div> </td> 
   <td> 
    <div>
      2 
    </div> </td> 
   <td> 
    <div>
      2 
    </div> </td> 
   <td> 
    <div>
      1 
    </div> </td> 
   <td> 
    <div>
      1 
    </div> </td> 
   <td> 
    <div>
      2 
    </div> </td> 
   <td> 
    <div>
      1 
    </div> </td> 
   <td> 
    <div>
      1 
    </div> </td> 
   <td> 
    <div>
      1. 
    </div> </td> 
  </tr> 
 </tbody> 
</table>

排序：

<table> 
 <tbody> 
  <tr> 
   <td> 
    <div>
      3 
    </div> </td> 
   <td> 
    <div>
      2 
    </div> </td> 
   <td> 
    <div>
      2 
    </div> </td> 
   <td> 
    <div>
      2 
    </div> </td> 
   <td> 
    <div>
      1 
    </div> </td> 
   <td> 
    <div>
      1 
    </div> </td> 
   <td> 
    <div>
      1 
    </div> </td> 
   <td> 
    <div>
      1 
    </div> </td> 
   <td> 
    <div>
      1. 
    </div> </td> 
  </tr> 
 </tbody> 
</table>

删除第一个数3：

<table> 
 <tbody> 
  <tr> 
   <td> 
    <div>
      2 
    </div> </td> 
   <td> 
    <div>
      2 
    </div> </td> 
   <td> 
    <div>
      2 
    </div> </td> 
   <td> 
    <div>
      1 
    </div> </td> 
   <td> 
    <div>
      1 
    </div> </td> 
   <td> 
    <div>
      1 
    </div> </td> 
   <td> 
    <div>
      1 
    </div> </td> 
   <td> 
    <div>
      1. 
    </div> </td> 
  </tr> 
 </tbody> 
</table>

把前面3个数减1：

<table> 
 <tbody> 
  <tr> 
   <td> 
    <div>
      1 
    </div> </td> 
   <td> 
    <div>
      1 
    </div> </td> 
   <td> 
    <div>
      1 
    </div> </td> 
   <td> 
    <div>
      1 
    </div> </td> 
   <td> 
    <div>
      1 
    </div> </td> 
   <td> 
    <div>
      1 
    </div> </td> 
   <td> 
    <div>
      1 
    </div> </td> 
   <td> 
    <div>
      1. 
    </div> </td> 
  </tr> 
 </tbody> 
</table>

排序：

<table> 
 <tbody> 
  <tr> 
   <td> 
    <div>
      1 
    </div> </td> 
   <td> 
    <div>
      1 
    </div> </td> 
   <td> 
    <div>
      1 
    </div> </td> 
   <td> 
    <div>
      1 
    </div> </td> 
   <td> 
    <div>
      1 
    </div> </td> 
   <td> 
    <div>
      1 
    </div> </td> 
   <td> 
    <div>
      1 
    </div> </td> 
   <td> 
    <div>
      1. 
    </div> </td> 
  </tr> 
 </tbody> 
</table>

删除第一个数1：

<table> 
 <tbody> 
  <tr> 
   <td> 
    <div>
      1 
    </div> </td> 
   <td> 
    <div>
      1 
    </div> </td> 
   <td> 
    <div>
      1 
    </div> </td> 
   <td> 
    <div>
      1 
    </div> </td> 
   <td> 
    <div>
      1 
    </div> </td> 
   <td> 
    <div>
      1 
    </div> </td> 
   <td> 
    <div>
      1. 
    </div> </td> 
  </tr> 
 </tbody> 
</table>

把前面1个数减1：

<table> 
 <tbody> 
  <tr> 
   <td> 
    <div>
      0 
    </div> </td> 
   <td> 
    <div>
      1 
    </div> </td> 
   <td> 
    <div>
      1 
    </div> </td> 
   <td> 
    <div>
      1 
    </div> </td> 
   <td> 
    <div>
      1 
    </div> </td> 
   <td> 
    <div>
      1 
    </div> </td> 
   <td> 
    <div>
      1. 
    </div> </td> 
  </tr> 
 </tbody> 
</table>

排序：

<table> 
 <tbody> 
  <tr> 
   <td> 
    <div>
      1 
    </div> </td> 
   <td> 
    <div>
      1 
    </div> </td> 
   <td> 
    <div>
      1 
    </div> </td> 
   <td> 
    <div>
      1 
    </div> </td> 
   <td> 
    <div>
      1 
    </div> </td> 
   <td> 
    <div>
      1 
    </div> </td> 
   <td> 
    <div>
      0 
    </div> </td> 
  </tr> 
 </tbody> 
</table>

删除第一个数1：

<table> 
 <tbody> 
  <tr> 
   <td> 
    <div>
      1 
    </div> </td> 
   <td> 
    <div>
      1 
    </div> </td> 
   <td> 
    <div>
      1 
    </div> </td> 
   <td> 
    <div>
      1 
    </div> </td> 
   <td> 
    <div>
      1 
    </div> </td> 
   <td> 
    <div>
      0 
    </div> </td> 
  </tr> 
 </tbody> 
</table>

把前面1个数减1：

<table> 
 <tbody> 
  <tr> 
   <td> 
    <div>
      0 
    </div> </td> 
   <td> 
    <div>
      1 
    </div> </td> 
   <td> 
    <div>
      1 
    </div> </td> 
   <td> 
    <div>
      1 
    </div> </td> 
   <td> 
    <div>
      1 
    </div> </td> 
   <td> 
    <div>
      0 
    </div> </td> 
  </tr> 
 </tbody> 
</table>

排序：

<table> 
 <tbody> 
  <tr> 
   <td> 
    <div>
      1 
    </div> </td> 
   <td> 
    <div>
      1 
    </div> </td> 
   <td> 
    <div>
      1 
    </div> </td> 
   <td> 
    <div>
      1 
    </div> </td> 
   <td> 
    <div>
      0 
    </div> </td> 
   <td> 
    <div>
      0 
    </div> </td> 
  </tr> 
 </tbody> 
</table>

依此类推：到最后只剩下：

<table> 
 <tbody> 
  <tr> 
   <td> 
    <div>
      0 
    </div> </td> 
   <td> 
    <div>
      0 
    </div> </td> 
   <td> 
    <div>
      0 
    </div> </td> 
   <td> 
    <div>
      0 
    </div> </td> 
  </tr> 
 </tbody> 
</table>

由此判断该序列是可图的。

发表评论取消回复

表情：

评论列表（有 0 条评论，146人围观）

还没有评论，来说两句吧...

相关阅读

相关试论微积分基本定理

目录摘要 I Abstract II 前言 1 第一章微积分基本定理发展历史 2 1.1巴罗的几何形式的微积分基本定理 2 1.2牛顿的反流数

Dear 丶/ 2024年03月31日 05:31/ 0 赞/ 104 阅读

相关图论

一、图的常用概念　　1、顶点（vertex）　　2、边（edge）　　3、路径　　4、无向图：顶点之间的连接没有方向　　![1007094-201909

柔光的暖阳◎/ 2023年10月10日 07:53/ 0 赞/ 88 阅读

相关图论基础

图图由节点和图构成；有向图：连线有方向；不对称性；无向图：连线无方向；是有向图的一种特殊请情况；有权图：连线有权值；无权图：连线无权值；简

柔情只为你懂/ 2023年08月17日 17:48/ 0 赞/ 175 阅读

相关数论，裴蜀定理

在数论中，裴蜀定理是关于最大公约数的一个定理，裴蜀定理得名于法国数学家艾蒂安·裴蜀。这个定理说明了，对任意整数a,b和他们的最大公约数d,存在一个关于 ax + by

秒速五厘米/ 2023年07月17日 12:35/ 0 赞/ 36 阅读

相关握手引理_图论中的握手引理–握手定理

![f70cd51f3ef71638ed52c52d56ef0a2a.png][] 握手引理 Hello Everyone, 大家好， Today we will se

港控/mmm°/ 2022年12月07日 12:57/ 0 赞/ 256 阅读

相关序列图与泳道图

我之前以为它们是同一种图。很傻很天真。一、先来一点直观的感受序列图 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdG

末蓝、/ 2022年11月14日 00:54/ 0 赞/ 211 阅读

相关图论

http://[blog.csdn.net/pipisorry/article/details/52518118][blog.csdn.net_pipisorry_articl

清疚/ 2022年09月25日 15:21/ 0 赞/ 283 阅读

相关图论（一）度序列与Havel-Hakimi定理

我一直想写一些关于图论学习的收获。一直由于这样或者那样的原因都没有开始。无论如何，现在开始吧！那么到底什么是图呢？我们这里说的图当然不是像照片一样的东东。最权威的定义：图=

古城微笑少年丶/ 2022年04月08日 15:49/ 0 赞/ 147 阅读

相关数据结构与算法——图论基础与图存储结构

![640?wx\_fmt=png][640_wx_fmt_png] 1 前言由于后续更新「面试专场」的好几篇文章都涉及到图这种数据结构，因此打算先普及一下图

左手的ㄟ右手/ 2022年02月28日 11:40/ 0 赞/ 300 阅读

相关图论算法

Problem1一笔画问题题目描述给出一个图，求其欧拉回路（若没有回路，则求其欧拉路径），若不存在则输出‘No solution’ 输入输入的第一

妖狐艹你老母/ 2022年01月06日 22:13/ 0 赞/ 301 阅读