圆方树

发布时间 2023-10-12 08:38:58作者: reclusive2007

圆方树的引入

我们知道,图没有很好的性质,而树有很多性质,并且容易通过很多方式来维护树上信息,因此将图上问题转化为树上问题是我们想要解决的。圆方树就是将图转化为树的数据结构。

圆方树的分类

圆方树分为两类:狭义圆方树广义圆方树

狭义圆方树

狭义圆方树是可以用来将仙人掌图转化为树的一种数据结构。

广义圆方树

广义圆方树是可以用来将所有无向图转化为树的一种数据结构。

狭义圆方树

作者还没学广义圆方树,所以先来讲狭义圆方树。

仙人掌图

什么是仙人掌图?这里给出定义:

任意一条边至多只出现在一条简单回路的无向连通图称为仙人掌。

简单来说,就是图中有环并且图中任意两个环没有公共边的图。

如果你还不懂的话请看下图。

image