我的问题是关于为什么每个 SSA 形式的程序默认都对应一个弦图。 Wikipedia defines弦图为
a chordal graph is one in which all cycles of four or more vertices have a chord, which is an edge that is not part of the cycle but connects two vertices of the cycle
这是一个取自 some lecture notes 的简单示例为了了解 SSA 表格注册分配的好处，我正在关注。作者写道:
[...] the following program and corresponding chordal graph:
首先:我不明白这个图怎么是弦的。我意识到该程序不是 SSA 形式。然后作者将其转化为SSA形式得到这张干涉图
但我还是看不出这是一个弦图，也看不出第一个图与后面的任何图有什么关系。
所有这些使得理解 SSA 程序如何产生弦交图变得非常困难。
以下是我调查过的一些来源:
最佳答案
关于您在讲义第 6 节中列出的程序:
I don't understand how is this graph is chordal. I realize that the program is not in SSA form.
您说得对，原始程序不是 SSA 形式。您也有理由对为什么它的“和弦图”是和弦感到困惑:不是。作者犯了一个小错误。他们在提到第一个程序时写的是“弦图”，他们的意思是写的是“干涉图”。
你指的第二张图是平凡弦图，因为它不包含任何循环。记住你给出的弦图的定义:
a chordal graph is one in which all cycles of four or more vertices have a chord, which is an edge that is not part of the cycle but connects two vertices of the cycle
如果有零个循环，则空洞地所有这些循环都包含一个和弦。
关于graph - 弦图和 SSA 形式程序，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/53559767/