如何解读这个图函数算法?
How to interpret this graph function algorithm?
所以我有一个 G 有向图(从节点 v 双向定向)和它的 Euler 巡回标记,如下所示:
我有一个名为 root(written_L,u)
的函数,其中 u
是目标 graph/component 的新根,而 written_L
是 Euler 巡回标记。所以root函数将u节点作为根,重新计算所有的边标签,给出一个新的欧拉游标签。
但是,我不能完全理解为根函数给出的算法:
以及对应的指称系统:
我试图为这个问题编写程序,但我无法完全理解这些数学表达式。如果有人能以非数学形式向我解释所有这些含义,我将不胜感激。
此外,如果需要,请随时询问更多信息。
有时候你需要的只是一个例子。下图是将根节点移动到中心列中间后的边缘标注。
您会注意到我们所做的只是从所有数字中减去 5。当原始标签至少为5时很好。当原始标签小于5时,我们需要减去5然后加上12,以保持标签在0到11的范围内。
因此,例如,曾经标记为 8 的边被重新标记为 8-5=3
。标记为 4 的边被重新标记为 4 -5+12 = 11
.
你需要知道的另一件事是减去 5(将结果保持在 0 到 11 的范围内)与加 7 模 12 相同。重复相同的例子,8 被重新标记为 (8+7) % 12 = 3
,并且 4 被重新标记为 (4+7) % 12 = 11
.
所以算法是:
- 求进入原根的最大标签,加1求模(M)。例子中最大的label是11,所以M是12.
- 找到离开新根 (Z) 的最小标签。在示例中 Z 为 5.
- 将增量 (D) 计算为
D = M - Z
。在示例中,D 为 7.
- 使用公式
newL = (L+D) % M
更新每个标签 (L)
所以我有一个 G 有向图(从节点 v 双向定向)和它的 Euler 巡回标记,如下所示:
我有一个名为 root(written_L,u)
的函数,其中 u
是目标 graph/component 的新根,而 written_L
是 Euler 巡回标记。所以root函数将u节点作为根,重新计算所有的边标签,给出一个新的欧拉游标签。
但是,我不能完全理解为根函数给出的算法:
以及对应的指称系统:
我试图为这个问题编写程序,但我无法完全理解这些数学表达式。如果有人能以非数学形式向我解释所有这些含义,我将不胜感激。 此外,如果需要,请随时询问更多信息。
有时候你需要的只是一个例子。下图是将根节点移动到中心列中间后的边缘标注。
您会注意到我们所做的只是从所有数字中减去 5。当原始标签至少为5时很好。当原始标签小于5时,我们需要减去5然后加上12,以保持标签在0到11的范围内。
因此,例如,曾经标记为 8 的边被重新标记为 8-5=3
。标记为 4 的边被重新标记为 4 -5+12 = 11
.
你需要知道的另一件事是减去 5(将结果保持在 0 到 11 的范围内)与加 7 模 12 相同。重复相同的例子,8 被重新标记为 (8+7) % 12 = 3
,并且 4 被重新标记为 (4+7) % 12 = 11
.
所以算法是:
- 求进入原根的最大标签,加1求模(M)。例子中最大的label是11,所以M是12.
- 找到离开新根 (Z) 的最小标签。在示例中 Z 为 5.
- 将增量 (D) 计算为
D = M - Z
。在示例中,D 为 7. - 使用公式
newL = (L+D) % M
更新每个标签 (L)