0%

仅供娱乐。

这里(如果无法访问,我只能说一句抱歉了)有一个表单,有一些与我相关的问题,每道题都标注了分数。

如果能有 70 分,我们就是好朋友(至少曾经),非常感谢你的关心,我不会忘记你的,我会珍惜共同创造的记忆,直至终结。

发布时间被我提前了一年,因为我不希望它出现在首页。

Ear decomposition 的定义见 Wikipedia。粗略地讲,在无向图中,耳朵就定义为一条路径,其中除了端点外的点的度数均为 2(端点可以重合),而且删去后不破坏图的连通性。耳分解就是将图中的耳朵依次删去直至删完,不是所有无向图都能被耳分解,同时耳分解的方案很可能是不唯一的。

充要条件

图中没有桥。必要性感受一下,还是显然的,证明就不证了。充分性可以用算法本身来证明,对于满足条件的无向图,算法一定能给出一个合法的耳分解。

Read more »

对于有向图 $G$(可能有环),其中起点 $r$ 可以到达所有点,当 $u$ 是所有到达 $v$ 的路径的必经点时,称 $u$ 支配 $v$。

可以构建支配树,其中每个点被所有它的祖先支配,又支配它子树中的结点。

Read more »