图荫度（英文是Arboricity of graph，海南琼州大学是我国开创先驱，现在这领域已是一个千军万马磅礴奔腾的非常广阔恢弘的领域如刚见在吞噬世界的图论的很多领域凌驾于人工智能等之上而前途辉煌的今年2021年毕业的杨燕平、刘娟2个博士和滕文顺、李萍、姜楠、张露等硕士的毕业学位论文的标题都全含“荫度”2字这几年还有山东大学博士许仁誉和谭香东南大学博士陶昉昀等等的博士学位论文也全都含有“荫度”-即图论一个领域到了现在的一年仍被这么多人把一生的命运押注在这领域这就已是不可思议。然而,在这领域在我国开创奠基之初的不易就如这里第3段的“精通英、俄、日、法和德语等5国语言也是精通计算机以及文体等的很多领域项目的天才数学家周尚超教授”在下面之艰难）：
在“荫度”的百度网页中最后的“定理4”就是海南琼州大学在这网www.qzu5.com/ac3.htm所附的论文上见收稿杂志注明1991年8月5日收到论文的结果。
在中国知网的主题或篇名输入“荫度”见我国第一篇论文是这里说的与习近平总书记组成中共中央政治局6人常委的李希的老师徐登洲教授等的1989年的论文。
“荫度”的第二篇论文是1990年的即这年我国只有一篇荫度论文并摘要全部文字内容就是“本文研究了图和补图的荫度间关系，并猜想：对p阶简单图G(V,E),a(G)+a(G¢)£1+[p/2]，其中G¢表示G的补图，a(G)表示G的荫度，[x]表示不小于x的最小整数”。
海南琼州大学的上面1991年8月5日投稿的论文就是完全彻底证明上面1990年的这猜想--也就是彻底解决上面论文的摘要的每一个字所隐含的问题（这是杂志注明1991年8月5日受到的投稿-而在此之前我也已投过其它杂志-并正如这里说这篇论文用了约100页证明-不过当时还没有电脑打印机而是手写在纸上的所以也不算太长（上面“1990年已被编入由最权威的世界数学家联合会编辑出版的世界数学家名录”的天才周尚超教授的这篇论文上注明比海南琼大更迟的1992年3月23日才收到投稿的正式出版这4页论文的3页证明了上面1990年的荫度猜想对“自补图的荫度”成立，但按这样的证明因象自补图这样的图类何止上千上万个甚至上百万个那要用多少页要证到何年才证完这猜想），而这里的约200页证明的才是电脑打印的A4纸5号字）。
现在已发展出很多方向，如在大规模图分析中，图的稠密度是决定算法复杂度与结构分析效果的核心指标之一。三角计数、k-clique 枚举、truss 分解、社区发现等经典任务，几乎都依赖某种稀疏性度量来界定算法复杂度。长期以来，荫度（arboricity）被用于衡量图稀疏性和界定上述算法复杂度的指标，但其计算复杂度高、工程代价大，难以直接应用于十亿条边的大规模真实图数据。为此，伪荫度（pseudoarboricity）作为一个“几乎等价但更易计算”的指标被提出。尽管如此，现有算法要么需要求解过多次的最大流，要么只能给出质量较差的 2-近似结果，在效率、精度与动态图维护之间始终难以兼顾。本文系统性地解决了这一问题：在静态与动态图上，高效、准确地计算并维护伪荫度。
荫度定义为将图的边划分为若干个互不相交的森林所需的最小数量。它在理论上非常优雅，但在实践中存在两大问题：（1）计算通常依赖拟阵理论，算法复杂、代价高；（2）对大规模动态图而言，几乎无法维护。
伪荫度将“森林”放宽为伪森林（每个连通分量至多包含一个环），具有四个关键性质：
（1）极强近似性：pseudoarboricity
等于
arboricity 或 arboricity − 1；
（2）可解释性强：它等于“最密子图的密度的向上取整”，其中密度（density）定义为子图的边数除结点数。相比之下，荫度于最密子图的密度的关系不直观；
（3）方向等价性：一个无向图的定向定义为将每条无向边分配一个方向得来的有向图，伪荫度等价于“所有图定向中，最小可能的最大入度”。
（4）可代替荫度界定复杂度：在下列常用图挖掘问题中，truss 分解计算、k-团枚举、结构图聚类、影响力社区，荫度 a 被用来界定其算法时间复杂度，论文证明在这些复杂度中伪荫度可直接替代荫度。
例：在下图中，考虑图(a)中的无向图，图(b)为森林划分，需要三个森林，所以荫度为3；图(c)为伪森林划分，需要两个伪森林，所以伪荫度为2；图(d)为一个拥有最小最大入度的定向，最大入度等于伪荫度等于2。
研究目标和贡献点我教学不如周教授的千分之一万分之一百万分之一辛苦，科研也不如，科研教授更不如北大哪些做长的千分之一。
论文目标：
（1）设计伪荫度的高效静态图算法；
（2）在动态图上高效维护伪荫度。
论文的贡献可以总结为以下三方面：
研究内容
现有方法
如下图所示，ReTest 算法可以通过构造流网络并计算最大流来回答“伪荫度是否 ≤ k”，运行一次 ReTest 算法的时间复杂度为 O(|E|^1.5)。
提出近似算法 INDEGREE，可以在近线性时间内得到伪荫度的近似值，实验表明在大部分情况下该近似伪荫度等于精确伪荫度；
论文将高质量近似算法与网络流方法相结合，大大减少了所需最大流运算的次数，使得精确算法相较现有 SOTA 方法获得最高 21 倍 的加速效果。
在动态图上，论文提出 INS / DEL 以及 INC /
INS++ 等多种动态图维护算法。在绝大多数更新场景下，仅需执行局部 BFS 即可完成维护，使伪荫度可在十亿级边动态图的实时维护。
改进方法
现有方法的弊端是需要调用的网络流次数过多，这是因为现有近似算法
DEGREE 的近似精度过差，使得必须需要二分搜索。论文设计了新颖的近似算法
INDEGREE，在实践中大部分情况能直接得出精确伪荫度，因此可显著减少最大流调用次数。
INDEGREE 算法的直观思路如下：伪荫度等于图定向的最小最大入度，说明可以用图定向的最大入度来近似伪荫度，尽可能地降低最大入度则能得到尽可能准确的伪荫度。INDEGREE
算法的伪代码如下，算法先初始化一个图定向，然后重复检查每一条有向边是否指向了高入度结点，如果是的话则反转这条有向边，这样既可降低高入度结点的度数。在一轮检查中，如果最大入度没有降低则停止检查。
在实验中，INDEGREE 算法经过最多 12 轮迭代即可获得很精确的伪荫度，在所有数据集上误差不超过 4，并在 8/10 个数据集上直接获得了精确的伪荫度。
因为 INDEGREE 的近似效果极佳，论文提出了新的计算精确伪荫度的方法：先调用
INDEGREE 获得近似伪荫度 p'，然后对 p', p'-1, p'-2 等依次调用最大流测试其是否为伪荫度，是的话则停止递减。INDEGREE
的极佳近似效果使得最大流的调用次数极少，因此可以省去二分搜索过程。
动态图维护伪荫度
在许多真实应用中，图结构并非静态，而是持续发生边的增加 / 消失。如果每次更新都调用静态算法计算伪荫度，成本很高。因此，高效的动态维护算法成为关键问题。
论文首次从理论到算法系统研究这一任务，并针对既有插入也有删除、仅有插入这两种场景分别设计高效动态算法，实现规模可达十亿边的动态图实时更新能力。
理论基础：伪荫度更新定理
论文首先提出伪荫度更新定理：在图中插入或删除一条边后，伪荫度的变化幅度最多为 1。这一定理说明不会出现“一条边导致全局密度结构剧变”的情况，并且在一次更新后只需回答伪荫度是否加一或伪荫度是否减一。
为了在动态图中避免频繁最大流计算，论文引入了一个关键概念：不可逆定向。其直观含义为：在当前图定向中，不存在一条路径，可以通过反转该路径使最大入度下降；一旦达到不可逆状态，当前最大入度恰好等于伪荫度。因此可将维护伪荫度的问题转化为维护一个不可逆定向的问题。
边插入 INS 算法
当插入一条边 (u,v) 时，算法首先将边指向当前入度较小的一端（假设为 v），尽量避免制造新的最大入度。然后，若插入后 v 的入度达到了当前最大入度，则尝试从该点出发，用 一次 BFS 寻找可逆路径；若找到，则反转该路径，恢复不可逆性；若找不到可逆路径，则伪荫度增加 1。
整个过程中最多反转一条路径，且 BFS 的搜索范围天然受限在图中的稠密区域，多数插入甚至无需 BFS，直接 O(1) 完成。因此，INS 的最坏复杂度为 O(m)，但平均性能接近常数级。
边删除 DEL 算法
删除算法的过程与 INS 类似，算法优先尝试通过寻找可逆路径进行局部 BFS 修复可逆性，其中的 BFS 过程同样受限在图中的稠密区域。只有在伪荫度确实下降时，才调用一次
ReTest（最大流）。在实际运行中，多数删除只需要 O(1) 完成，即不需要 BFS 进行路径修复，仅有极少数情况需要调用最大流，因此平均性能仍接近常数级。
单插入场景的 INC 与 INS++
算法
在许多应用中，图的边是仅插入不删除的。针对这一重要特例，论文进一步设计了两种增量算法：
INC：简单且高效。算法只需关注入度是否达到 p+1；
若能找到可逆路径则修复；否则直接提升 伪荫度。算法逻辑极简，最坏复杂度为 O(m) ，实践中非常快。
INS++：额外维护一个“近最密子图”的结构 D_top，包含所有入度等于 p 或能到达这些结点的顶点。通过 D_top
可以在 O(1) 时间判断是否“有必要 BFS”，跳过大量无意义搜索。论文证明：D_top 的密度与最密子图的密度的差值不超过 1，这使 INS++
同时具备结构解释性与极致性能，甚至比 INC 更快速。
所以，算法非常已重要。在下附一些世界权威是算法名著：
这页简概计算理论、算法以及数据结构（现在已是的时代，就如仅存的中国计算机学会唯一名誉理事长李国杰院士说计算机科学“成也算法,败也算法”，更有“这个世界,一切皆可计算”—而与海南琼大所做学科有关的这里见几个计算机科学之父创造的就是这一切的主要基石大厦。还如我们读研时代的全球图论界学子学者们必定是以J. A. Bondy和U. S. R. Murty的《图论及其应用》为这学科首选用书而这《图论及其应用》的第一章第1篇参考文献就是下面要说的1986年计算机诺贝尔奖图灵奖得主John
Hopcroft等的《计算机算法的设计与分析》一书、这《图论及其应用》的第二章第2篇参考文献就是下面要说的现代计算机科学鼻祖Donald Knuth的被誉为“算法圣经”的《计算机程序设计艺术 第三卷》一书):
先讲这页附件下撰写“数据结构”圣经的海南琼州大学的导师柳柏濂教授去合作几年的威斯康辛大学的博士E.
Horowitz大师的《计算机算法基础》（邹海明85年版及崔国华等的书均说只有这书…，由冯博琴译它--刚见北大用的第1、2本书是它俩-但“专题选讲”仅讲简介).
这些领域公认的重要著作还有：哈佛学院院长的Harry
Lewis和Christos Papadimitriou院士的《Elements of the Theory of Computation计算理论基础》，这书只有3个结果以人名冠之,其中第1个是:这里来信表达很高兴(他的第2封信更知当时杂志仍…)担任我们海南琼州大学编委的美国数学会主席Anil Nerode的定理2.5.2 Myhill-Nerode定理（就如这页的第3说“哈佛学院院长Lewis和比尔·盖茨的老师Papadimitriou合写的《计算理论基础》一书中仅有Myhill-Nerode定理、计算机诺贝尔奖得主Cook等的3个定理结论是以人名命之”）。它的作者Harry
Lewis自不久前的1995年起担任Dean of Harvard College哈佛学院院长-也看到他的博士中有第2代博士的3人的论文题目全都做Combinatorics组合数学，这书另一作者Christos Papadimitriou的博士论文是组合数学优化的并是美国三院院士,他也是世界首富比尔·盖茨的老师并更和比尔·盖茨合作发表我们组合数学论文-这是比尔·盖茨创立微软前的唯一科学论文）；
如此,除了Papadimitriou的上面这书，我们组合数学学人读研究生时还会读和世界首富比尔·盖茨唯一合作论文的美国三院院士Papadimitriou和普林斯顿大学前辈Kenneth Steiglitz合写的《组合最优化:算法和复杂性》这本世界名著（这名著的翻译者是来信高度评价我们海南琼州大学做出世界一流水平的我国哈密顿图主要开拓者中科院刘振宏大师-即于1988年翻译为中文版630页巨著）。
我也有这美国三院院士Papadimitriou以及计算机理论界的第二名师Umesh Vazirani和哈佛大学最优等本科毕业的他的博士S. Dasgupta最近合撰出版的《算法概论》。
还有博士论文做平面图论算法的1986年计算机诺贝尔奖图灵奖得主Robert
E Tarjan的名著《Data
structures and network algorithms》就是结合图论的许多些领域构建的书,他在图论算法和数据结构领域有很大的贡献，他的唯一华人博士就做极值图论问题
关于可计算理论，开头已说我也有另一支流是和海南琼州大学合作多篇SCI论文的Thulasiraman院士1981年出版的《图、网络与算法》第十五章的参考文献中5个文献的第一作者都是1986年图灵奖得主John
Hopcroft统帅的（这是1981年出版的-其后修改版的收入应更多），即他和Alfred Aho，Jeffrey
Ullman合写的《计算机算法的设计与分析》英文版书籍（即上面说的我们图论人以前用的Bondy和Murty的图论书的第一章第1篇参考文献就是书,并这书许多内容也与这里的20世纪最伟大的十大算法很有关系），其中作者Aho是2院院士兼美国工程院计算机与工程部主席，John
Hopcroft是1986年计算机诺贝尔奖图灵奖得主美国3院院士，Jeffrey Ullman是美国3院院士）；我也有他们仨人合写的《数据结构与算法》，以及后2个作者John
Hopcroft，Jeffrey Ullman合撰前2版并第三版加入Rajeev
Motwani合写的《自动机理论、语言和计算导引》一书的1979年中文版和1986年中文版528页我都读了多遍并最近又再出新的中文版的内容仅微调读它应也没问题（就是新加入的第三作者Rajeev
Motwani，他的博士中培养博士最多的David Karger在哈佛读本科并在斯坦福的博士论文做图论优化--图论也应用于搜索引擎且图论还是理解大数据的关键[之关键就如Roy Marsten大师的文章第一行是全球第5名的Facebook创始人Zuckerberg正在展示图论搜索]--更有比他的这图论博士David Karger低几届的2个同系博士即多次居世界第一企业的搜索巨头Google的两个创办人就由这Rajeev
Motwani做创业顾问和导师，Rajeev
Motwani最近合撰《随机算法》，可惜英年早逝否则也获诺贝尔奖，如最近得4亿美元融资的美国两院院士“AI先驱”即a pioneer
in the field of machine learning的Daphne
Koller大师都以被授予Rajeev Motwani Professor为荣！）。
还有,我也有的现代计算机科学鼻祖Donald
Knuth在1985年前出版的前3卷包括中文版：《计算机程序设计艺术 第三卷》（就是上面说的Bondy和Murty的图论书引用的书）、《计算机程序设计技巧 第一卷:基本算法》、《计算机程序设计艺术 第二卷:半数值算法》(英文版)的部分内容也与这里的20世纪最伟大的十大算法有关系。进入21世纪Knuth好象又出版：计算机程序设计艺术:第4卷第0册组合算法与布尔函数导论; 第4卷第A册组合数学算法; 第4卷第2册生成所有元组和置换-(这是元组组合问题-每次置换也是一次组合); 第4卷第3册生成所有组合和划分; 第4卷第4册生成所有树-组合数学生成史--所以,这5本书竟然全是组合数学的；
王浩大师在哈佛大学的博士Shimon Even的为研究生教学用的著作《图论算法》（在前言说本书的工作受到1986年的图灵奖获得者John
Hopcroft、1985年的图灵奖获得者Richard
M. Karp、1986年的图灵奖获得者Robert
E·Tarjan等的影响）
再有一个支流-普林斯顿大学计算机系的创始人首任系主任Robert
Sedgewick和法国科学院院士Philippe
Flajolet的《算法分析导论》，正如计算机科学鼻祖Donald Knuth说“Sedgewick和Flajolet写的这本众人翘首以盼的教科书也因此备受欢迎。本书的作者不仅仅是这个领域的世界级专家，同时也是算法分析的布道大师。我坚信，这本书会让每一位细细品读的计算机研究人员从中获益。D. E. Knuth”；普林斯顿大学创始系主任Robert Sedgewick还独撰《图论算法》一书，而法国院士Philippe Flajolet为第一作者撰写《Analytic
Combinatorics分析组合数学》一书（Philippe Flajolet的伟大工作可参考1978年博士毕业到1997年都在维也纳工业大学的Helmut
Prodinger和美国普渡大学Szpankowski教授1998年就已在Algorithmica算法杂志发表的介绍性论文“Philippe Flajolet's Research in
Analysis of Algorithms and Combinatorics”）。法国科学院院士总名额最多110名，不过这三本书中我只有前2本-法国院士的第3本要一千多元。
Donald Knuth的博士Vaughan Pratt的博士David Harel在80年代出版的《算法学》和上面528页等的都有些不同领域就象最后部分“更宏伟蓝图”共3章等可组成更强大广泛宏伟的蓝图（这个评论、这个评论、这个评论等等都高度评价这书，我们图论组合学科的计算机科学鼻祖Donald Knuth的这徒孙David
Harel已是美国三院院士英国皇家学会院士以色列科学院副院长刚见又担任以色列科学院院长，可别看以色列总人口仅约900万人--而我们海南省人口约1000万，可以色列的科技…就如分布在全球的以色列人总共获得162枚诺贝尔奖，约占全球诺贝尔奖总数的20%）。
当然, Thomas Cormen，Charles Leiserson，Ronald
Rivest，Clifford Stein的《算法导论》是最全面的算法书,专搞算法的或时间很充裕的就应全读,没时间就选读也行(其余作者都没甚名气但第3作者Ronald Rivest罗纳德·李维斯特的名气却震天并获得图灵奖-他的博士中最著名的Blum,Avrim的博士论文做图论着色-其父亲是诺贝尔奖得主但这小子是否志短怎跑去当一个小小的芝加哥丰田理工学院首席学术官-虽也算是全校第2号人但小地方难做大科学)；还有,最近2个都是美国科学院、工程院、艺科与科学院的三院院士Jon
Kleinberg和Eva Tardos合写的《算法设计》被北京大学计算机系主任屈婉玲说这是我看到过的最好教材的并它一共12章每章都主要讲图论哈密顿图等（可知他们为啥全都成美国三院院士！这可能绝不仅有的,2个合写的都成三院院士,要知一个人既兼科学又兼工程已够难，其中第一作者Jon Kleinberg的博士论文做Disjoint Paths Problems其最长的是Disjoint哈密顿圈即哈密顿图；第二作者Eva Tardos的导师András Frank的导师László Lovász就是在这里的哈密顿图专家小Katona的导师）。
我也有麻省理工学院科学学院院长Michael Sipser的世界名著《计算理论导引》（这Michael Sipser的较年轻却是成就最大的博士Spielman,Daniel就做我的导师的图谱论而成为信息科学第8个诺贝尔奖获得者）,等等:
正如图灵奖得主Nicklaus Wirth说:算法+数据结构=程序,如此,学了算法和数据结构,我就也早就有他的《算法+数据结构=程序》,以及Brian
W. Kernighan和图灵奖得主Dennis M. Ritchie的《C程序设计语言》,等等（不过, 因人生的时间有限，所从事工作在偏理论和偏动手之间,只能有所偏重，实为人生遗憾，就使你极喜好被评选为20世纪最佳12部学术专著之一的这里的我们现代哈密顿图先驱Ore的徒孙Donald
Knuth的巨著《计算机程序设计的艺术》）。
为什么我们海南琼州大学以前居世界领先的图论以及组合数学占有如此分量，这也就如施伯乐教授和蔡子经教授的《数据结构教程》共250页书中第五至第七章(第100-235页)占全书一半就专讲树和图论，树也是图论的主要领域--可见图论仅在数据结构中的应用就占其一大半作用，而图论仅是Combinatorics组合数学的一个主要分支。（而数据结构应用的广泛性就如北大许卓群等人在其《数据结构》说第十四到十八章在内容上与后续的操作系统、数据库系统课程会有一定的重叠）。 哈佛大学2个组合数学大师Andrew
Gleason和Gian-Carlo
Rota的组合数学博士Daniel I. A.
Cohen既独自写《组合数学理论基本技术》也独立撰写838页的《计算机理论导论》；并行计算-居于其核心的国家北大清华等都设有的高性能计算中心并参看全球超级计算机排行榜)。
这就因如各类计算机算法书籍等在讲算法复杂性都会优先讲中国科学院大学常务校长在这里区块链比特币的最后段的周游世界问题/以及旅行商问题/等等都是以前我们海南琼州大学居世界领先的哈密顿圈问题的一些特例问题
能举出比上面算法书更权威著名的吗？可见,深刻理解图论和组合数学,将是计算机和很多相关学科取得新的重要发展和突破的关键(也就,图论和组合数学的许多重要作用仍待人们去理解和发现，正如顶礼膜拜即算法如此之至上,是正如李国杰院士说计算机科学“成也算法,败也算法”，要知李国杰院士是中国计算机学会唯一一个在世的名誉理事长--另一名誉理事长张效祥院士2015年已逝世，可计算理论的作用也如这里见几个计算机科学之父都是主要基于它的工作而奠定他们的地位的)。
关于可计算理论和算法，可参考这个网页、以及这个网说到的3个获得图灵奖的师兄弟的计算理论书籍，及其这个网也说到另一些计算机理论书籍及其与图论关系，还有这个网的计算机理论书籍，也可参考这中国第一个组合数学研究室的下面部分的计算机理论书籍等等。