圆方树学习笔记


前世今身

要说圆方树最早被提出,这个可能需要追溯到这篇论文的发布,论文是:《Maintaining bridge-connected and biconnected components on-line》。

这篇论文的作者是Westbrook, Jeffrey / Tarjan, Robert E.。没错,是我们熟知的那个 Tarjan 。

似乎圆方树又会与 Tarjan 算法有不解之缘了。

而他在国内被大规模地推广使用,是在 WC2017 的营员交流中 immortalCO 和 WrongAnswer 做了 《Making Graphs into Trees》的报告。

概念

仙人掌

如果一个无向连通图的任意一条边最多属于一个简单环,我们就称之为仙人掌。

而所谓简单环指的是不经过重复的结点的环。

下面这张介绍仙人掌的图,大家肯定都不陌生了。

圆方树

树的概念大家肯定都很清楚。

那么圆方树其实就是由圆点和方点所构成的一棵树。

通俗的定义是:

  • 圆点,是指仙人掌中本来存在的点;
  • 方点,是一个环所对应的虚点,通过将环上所有的点连向这个虚点来表示仙人掌中的环。

如果用比较标准化的数学方法来定义

构造方式

 

You may also like

LEAVE A COMMENT

Statistics

  • 0
  • 67,592

Categories

Archive

Comments