图变换单元概述

### 图变换单元概述 #### 1. 图变换规则基础 在图变换中，有两个重要的规则：`start`和`run`。`start`规则用于移除无标签的循环，并在同一节点添加开始循环和结束循环；`run`规则则是用`p`边替换无标签边，移除左侧的两个循环，并在右侧目标节点添加结束循环，同时会保持边的方向不变。 图变换规则应用于图`G`的过程包含以下三个步骤： 1. 选择`L`在`G`中的一个单射匹配`g(L)`。 2. 移除`gV(VL - VK)`中的节点，以及`gE(EL - EK)`中的边和与移除节点相关的边，得到中间图`Z ⊆ G`。 3. 通过在`g(K)`处将`Z`与`R`粘合，将右侧`R`添加到`Z`中，得到图`H = Z + (R - K)`，其中`VH = VZ + (VR - VK)`，`EH = EZ + (ER - EK)`。`Z`中的边保持其标签、源和目标，`R`中的边也保持其标签，若源和目标属于`VR - VK`则保持不变，否则`sH(e) = g(sR(e))`（对于`e ∈ ER - EK`且`sR(e) ∈ VK`），`tH(e) = g(tR(e))`（对于`e ∈ ER - EK`且`tR(e) ∈ VK`）。 规则`r`应用于图`G`表示为`G =>r H`，这被称为直接推导。若上下文明确，下标`r`可省略。给定有限规则集和有限图`G`，单射匹配的数量受`G`大小的多项式限制，构建直接推导图的时间复杂度为线性，因此找到匹配和构建直接推导需要多项式时间。 以下是一些直接推导的示例： | 初始图 | 规则 | 推导后图 | | ---- | ---- | ---- | | G1 | run | G12 | | G2 | run | G23 | | G2 | run | G24 | | G3 | run | G34 | | G4 | run | G41 | | G12 | run | G123 | | G12 | run | G124 | | G23 | run | G234 | | G24 | run | G241 | | G34 | run | G341 | | G41 | run | G412 | | G123 | run | G1234 | | G234 | run | G2341 | | G341 | run | G3412 | | G412 | run | G4123 | `start`规则可应用于`G0`四次，分别得到`G1`、`G2`、`G3`和`G4`。 #### 2. 推导与应用序列 直接推导的顺序组合称为从`G0`到`Gn`的推导，可表示为`G0 =>*P Gn`，字符串`r1···rn`是推导的应用序列。例如以下推导： - `G0 => G1 => G12 => G123 => G1234` - `G0 => G1 => G12 => G124` - `G0 => G2 => G23 => G234 => G2341` - `G0 => G2 => G24 => G241` - `G0 => G3 => G34 => G341 => G3412` - `G0 => G4 => G41 => G412 => G4123` 这些推导表明，通过应用一次`start`规则和`k`次`run`规则（`k ∈ {0, 1, 2, 3}`），可以从`G0`推导出`SP(G0)`中的所有图。其中，六个推导图对应`G0`的死端简单路径，四个图`G1234`、`G2341`、`G3421`和`G4123`表示`G0`的哈密顿路径。 #### 3. 简单图变换单元 规则在图上产生二元关系，规则集产生一组推导。为了更好地对图上的过程进行建模，需要初始图、终端图和控制条件，这引出了简单图变换单元的概念，图语法是其重要的特殊情况。 ##### 3.1 图语法 图语法是一个系统`GG = (S, P, Δ)`，其中`S`是初始图，`P`是有限的图变换规则集，`Δ ⊆ Σ`是终端符号集。其生成的语言`L(GG)`由所有标记在`Δ`上且可从初始图`S`通过连续应用规则`P`推导得到的图组成。 例如，以下图语法： ```plaintext unlabeled graphs initial: empty rules: new-node = empty ⊇ empty ⊆ new-edge = ⊇ ⊆ terminal: {*} ``` 该语法生成每个节点带有单个无标签循环的无标签图。初始图为空图，`new-node`规则每次应用添加一个带无标签循环的节点，`new-edge`规则在两个节点之间添加边，由于只考虑单射匹配，不会产生新的循环。终端表达式`{*}`指定所有无标签图，因此所有推导图都属于生成的语言。 ##### 3.2 图类表达式 图类表达式是指定图类的语法实体，常见的图类表达式包括： - 子集`Δ ⊆ Σ`，`SEM(Δ) = GΔ ⊆ GΣ`。 - 禁止结构`forbidden(F)`，`SEM(forbidden(F))`包含所有不存在从`F`到`G`的图态射的图`G`。 - 规则集`P`，`SEM(reduced(P))`包含所有不能应用`P`中任何规则的`P`约简图。 - 图语法`GG`本身，`SEM(GG) = L(GG)`。 ##### 3.3 控制条件 控制条件用于减少推导过程的不确定性，常见的控制条件有： - 规则集上的正则表达式，推导的应用序列`s`若属于正则表达