支配

✍ dations ◷ 2025-04-03 12:28:35 #图论

在计算机科学中,控制流图的一个节点 d 支配节点 n,当且仅当从开始节点(可以理解为源)到节点 n的每一条路径均要经过节点d,写作d dom n (一写作d {\displaystyle \gg } n)。根据上述定义,容易得到每个节点均控制其自身。

一些相关概念:

一般而言,我们会使用 Tarjan 算法在 O ( | V | + | E | ) {\displaystyle O(|V|+|E|)} 的时间内将其求出

首先来介绍一些这个算法的大概步骤

我们用 idom 表示点 x {\displaystyle x} 的最近支配点,用 semi 表示点 x {\displaystyle x} 的半必经点。

那什么是半必经点呢?

对于一个节点                     Y              {\displaystyle Y}  ,存在某个点                     X              {\displaystyle X}  能够通过一系列点                               p                      i                                {\displaystyle p_{i}}  (不包含                     X              {\displaystyle X}                      Y              {\displaystyle Y}  )到达点                     Y              {\displaystyle Y}  且                             i                 d        f        n                >        d        f        n                      {\displaystyle \forall i\ dfn>dfn}  ,我们就称                     X              {\displaystyle X}                      Y              {\displaystyle Y}  的半必经点,记做 semi=X

当然一个点的“半必经点” X {\displaystyle X} 会有多个,而且这些半必经点一定是搜索树中点 X {\displaystyle X} 的祖先。

对于每个点,我们只需要保存其半必经点中最小的一个,下文中用表示点的半必经点中值最小的点的编号。

我们可以更书面一点的描述这个定理:

计算机科学中支配的概念第一次被提出是在Reese T. Prosser在1959年一篇关于流网络的论文中提出的 而在此论文中,Prosser并未提出一种有效算法以计算支配关系,解决这一问题的有效算法直到十年后才被 Edward S. Lowry and C. W. Medlock 提出。Ron Cytron等人在1989年将其应用于高效计算应用于静态单赋值形式的φ 函数时对其重新燃起了兴趣。

4.https://blog.csdn.net/a710128/article/details/49913553

相关

  • 林奈氏分类系统二名法(英语:Binomial Nomenclature,Binominal Nomenclature 或 Binary Nomenclature),又称双名法,依照生物学上对生物种类的命名规则,所给定的学名之形式,自林奈《植物种志》(1753
  • 平衡点在数学中,平衡点是相对微分方程或差分方程的概念。对于微分方程若 f ( t ,
  • 埃及第一王朝第八第十古埃及第一王朝连同第二王朝通常被纳入为早王朝时期。在这段时期,埃及的首都在提尼斯(Thinis)。埃及第一王朝法老列表有关这个时期的资料乃来自少数的遗址及其他刻有法
  • 摇滚摇滚(英语:rock and roll/rock 'n' roll/ rock & roll)是一种音乐类型,起源于1940年代末期的美国,1950年代早期开始流行,迅速风靡全球。摇滚乐结合了当时流行的非裔美国人蓝调、乡村
  • 三世三世间再与“百界千如”配合即构成“三千世间”,这也是天台宗“一念三千”的思想基础,《摩诃止观》:“夫一心具十法界,一法界又具十法界,即成百法界,一界具三十种世间,百法界即具三
  • span class=nowrapHo(NOsub3/sub)sub3/sub/span硝酸钬是一种无机化合物,化学式为Ho(NO3)3。硝酸钬可以将氧化钬、氢氧化钬或碳酸钬溶于硝酸得到:所得溶液经过小心蒸发可以得到水合硝酸钬,其中六水合物最常见。水合硝酸钬受热
  • 阳和阳和(1635年十月—1643年十月),是大越国后黎朝神宗黎维祺的第三个年号,共计7年。
  • 圆台圆台,又称截顶圆锥、圆亭,是几何学中研究的一类三维形体,指一个圆锥被平行于它的底面的一个平面所截后,截面与底面之间的几何形体。截面也称为圆台的上底面,原来圆锥的底面称为下
  • font color=white马来西亚/font马来西亚大学列表如下:所有坐标的地图 - OSM 所有坐标的地图 - Google 所有上至200个坐标的地图 - Bing3°08′17″N 101°36′25″E / 3.1379367°N 101.6070017°E / 3.137
  • 低出生体重儿低出生体重儿(LBW)定义为出生体重小于2500克(5.5磅)的新生儿。 低出生体重通常由早产(通常定义为出生时胎龄小于37周)或/和小于胎龄(即产前生长速率放缓)或者由这两种原因综合造成的