如何做网站推广最有效,公众号平台官网登录,贵阳做企业网站,门户网站推广优势转自http://sbp810050504.blog.51cto.com/2799422/883904 我一直想写一些关于图论学习的收获。一直由于这样或者那样的原因都没有开始。无论如何#xff0c;现在开始吧#xff01;那么到底什么是图呢#xff1f;我们这里说的图当然不是像照片一样的东东。最权威的定义现在开始吧 那么到底什么是图呢我们这里说的图当然不是像照片一样的东东。最权威的定义图顶点集合边集合。换言之凡是能抽象成点集合和边集合的东 西都是图。比如中国地图。地图上的城市是一个个的点而任意两个相邻城市之间有路。那么地图就是很直观的一种图。为了更方便的表示我们引入了英语单 词。Vertext(顶点),Edge(边)Graph图。不管什么图就可以用GV,E表示了。 地图是一种图中国的七大水系网也是一种图。很多湖泊可以视为点而长江、黄河这些可以看作边。由于水流基本上是单向的(当然也有倒流的情况这里我们理 想化就忽略了)所以像这样边有方向的图我们称为有方向的图长江水只能从喜马拉雅流向东海而绝对不会反过来的简称有向图。如果边没有方向那当 然称为无向图了。 我们还是回到地图。都说条条大路通北京你说罗马也没错那么有到底有多少条路到北京呢在图论里把这样连接到一个点的边的数量比如连接到北京的路称为度 对于图的所有顶点我们可以统计出每个顶点的度。像这样的一串数字我们称之为度序列。那么反过来给定一个序列能否判断这个序列是可图的 呢这里有一个定理Havel-Hakimi定理可以用来判定一个序列是否可图。Poj1659就是用Havel-Hakimi解决的。 Havel-Hakimi定理的内容可百度之。 例题POJ-1659 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】把区间【16】中的数删除。序列变成 下标 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 由此判断该序列是可图的。 转载于:https://www.cnblogs.com/gj-Acit/archive/2013/03/06/2946190.html
