我一直想写一些关于图论学习的收获。一直由于这样或者那样的原因都没有开始。无论如何，现在开始吧！
那么到底什么是图呢？我们这里说的图当然不是像照片一样的东东。最权威的定义：图=顶点集合+边集合。换言之，凡是能抽象成点集合和边集合的东西都是图。比如：中国地图。地图上的城市是一个个的点，而任意两个相邻城市之间有路。那么地图就是很直观的一种图。为了更方便的表示，我们引入了英语单词。Vertext(顶点),Edge(边)，Graph（图）。不管什么图，就可以用G<V,E>表示了。
地图是一种图，中国的七大水系网也是一种图。很多湖泊可以视为点，虚拟主机，而长江、黄河这些可以看作边。由于水流基本上是单向的(当然也有倒流的情况，这里我们理想化就忽略了)，美国空间，所以，像这样：边有方向的图我们称为有方向的图（长江水只能从喜马拉雅流向东海，而绝对不会反过来的）简称有向图。如果边没有方向，那当然称为无向图了。
我们还是回到地图。都说条条大路通北京（你说罗马也没错），那么有到底有多少条路到北京呢？在图论里，把这样连接到一个点的边的数量（比如连接到北京的路）称为：度！
对于图的所有顶点，我们可以统计出每个顶点的度。像这样的一串数字，我们称之为：度序列。那么反过来，给定一个序列，能否判断这个序列是可图的呢？这里有一个定理：Havel-Hakimi定理可以用来判定一个序列是否可图。Poj1659就是用Havel-Hakimi解决的。
Havel-Hakimi定理的内容可百度之。
Havel-Hakimi定理很容易理解：
三步走就可以了：
比如序列：4 7 7 3 3 3 2 1
下标
1
2
3
4
5
6
7
8
值
4
7
7
3
3
3
2
1
第一步：把序列按降序排序。
下标
1
2
3
4
5
6
7
8
值
7
7
4
3
3
3
2
1
第二步：删除第一个数7。序列变成
下标
1
2
3
4
5
6
7
值
7
4
3
3
3
2
1
第三步：从头开始，数7个数，也就是下标：[1,7]把[1,7]区间里的值都减1
由于第一个数已经删除，那么序列变成这样的了：
下标
1
2
3
4
5
6
7
值
6
3
2
2
2
1
0
然后：
重复第一步：排序。
重复第二步：删除第一个数6
重复第三步：从头开始数6个数：也就是下标【1,6】，把区间【1，6】中的数删除。序列变成：
下标
1
2
3
4
5
6
值
2
1
1
1
0
-1
由于已经出现了-1，而一个点的边数（度）不可能为负数。所以，香港服务器，我们就可以判定序列无法构成一个图，所以此序列是不可图的。
下面再举一个例子：
已经排序：
5
4
3
3
2
2
2
1
1
1.
删除第一个数5：
4
3
3
2
2
2
1
1
1.
把前面5个数减1：
3
2
2
1
1
2
1
1
1.
排序：
3
2
2
2
1
1
1
1
1.
删除第一个数3：
2
2
2
1
1
1
1
1.
把前面3个数减1：
1
1
1
1
1
1
1
1.
排序：
1
1
1
1
1
1
1
1.
删除第一个数1：
1
1
1
1
1
1
1.
把前面1个数减1：
0
1
1
1
1
1
1.
排序：
1
1
1
1
1
1
0
删除第一个数1：
1
1
1
1
1
0
把前面1个数减1：
0
1
1
1
1
0
排序：
1
1
1
1
0
0
依此类推：到最后只剩下：
0
0
0
0
由此判断该序列是可图的。
本文出自 “每天进步一点点” 博客，请务必保留此出处
经受雨，面对另一个轮回。
