1 基本定义
1.1 关系的直观含义
可达关系用来描述对象之间“能否通过若干中间步骤到达”的联系。直观上，如果从一个点、一个状态或一个对象出发，经过若干次转移能够到达另一个对象，那么二者之间就存在可达性。这个概念强调的不是“直接相连”，而是“经过有限次中转后能够相连”。
在实际语境中，可达关系常被用来表达路径、推理链、状态演化或操作序列是否存在。由于它关注的是间接连接，因此比单一步骤的关系更能反映整体结构。
1.2 可达关系的形式化定义
在形式化研究里，可达关系通常建立在一个基本关系之上。设有集合 \(A\) 及其上的二元关系 \(R\)，若存在从元素 \(x\) 到元素 \(y\) 的有限步骤序列，使得每一步都满足关系 \(R\)，则称 \(y\) 对 \(x\) 可达。由此得到的关系通常记为 \(R^*\) 或相关记号，具体含义取决于是否包含“零步到达”。
1.2.1 基于有限步转移的定义
若从 \(x\) 到 \(y\) 存在长度为 \(n\) 的转移序列 \(x=x_0, x_1, \dots, x_n=y\)，并且对每个 \(i\) 都有 \(x_i R x_{i+1}\)，则称 \(y\) 可由 \(x\) 经过有限步到达。这里的 \(n\) 可以是正整数；若允许 \(n=0\)，则表示对象自身也被视为可达。
这种定义最符合“沿着边走若干步”的直觉，在图论和自动机理论中尤为常见。
1.2.2 基于关系复合的定义
另一种定义方式是通过关系复合来描述。若 \(R^n\) 表示关系 \(R\) 与自身复合 \(n\) 次，那么可达关系就是这些幂次关系的并集。也就是说，只要存在某个有限的 \(n\)，使得 \(x R^n y\) 成立，就认为 \(y\) 对 \(x\) 可达。
这种表述更适合代数化处理，便于证明性质、构造闭包以及进行算法设计。
1.3 相关符号与记法
可达关系在不同学科中有多种记法。常见写法包括箭头表示和闭包表示，两者都用于强调“经过有限步后可以到达”的含义。由于文献传统不同，符号可能略有差异，但核心思想基本一致。
1.3.1 箭头表示法
在图论或状态转移系统中，常用箭头表示从一个对象到另一个对象的可达性。例如，若写作 \(x \to y\)，通常表示存在一步转移；若写作 \(x \to^* y\)，则表示存在零步或多步转移后的可达关系。某些文献还会用 \(x \Rightarrow y\) 或类似符号表达间接到达。
1.3.2 闭包表示法
在关系代数中，可达关系常视为基本关系的传递闭包或反身传递闭包。常用记号包括 \(R^+\) 和 \(R^*\)：前者通常表示正闭包，即至少一步可达；后者通常表示反身传递闭包，即允许零步到达。不同著作中符号约定可能略有变化，因此需要结合上下文理解。
2 数学性质
2.1 反身性
若采用反身传递闭包的定义，可达关系通常具有反身性，即任意元素都可从自身到达自身。这对应“零步转移”的解释。若只取正闭包，则反身性一般不成立，因为对象未必能通过至少一步回到自己。
2.2 传递性
可达关系最重要的性质之一是传递性。若 \(x\) 可达 \(y\)，且 \(y\) 可达 \(z\)，那么 \(x\) 也可达 \(z\)。这正是“可通过若干步继续延伸”的自然结果，因此可达关系往往是传递闭包意义下的标准对象。
2.3 自反传递闭包
自反传递闭包是从原关系出发，在尽量少增加额外边的前提下，使其同时满足反身性与传递性的最小关系。它在理论与计算中都非常重要，因为它把“直接一步关系”扩展为“任意有限步关系”。
2.3.1 与原关系的包含关系
原关系通常包含在其自反传递闭包之中。也就是说，若 \(xRy\) 成立，那么在闭包关系下，\(x\) 到 \(y\) 的可达性也成立。闭包并不否定原有联系，而是将其扩展到更高层次的间接连接。
2.3.2 最小性性质
自反传递闭包具有最小性：在所有包含原关系且同时反身、传递的关系中，它是最小的一个。这个性质使其成为一种标准化构造，便于统一讨论路径可达、状态演化与推理闭合。
2.4 对称性与非对称性
可达关系一般不要求对称。若 \(x\) 可达 \(y\)，并不必然意味着 \(y\) 也可达 \(x\)。在有向图中，这种单向性十分常见。只有在特殊结构下，例如某些双向连通系统，才可能出现对称可达。
同时，可达关系也可能表现出非对称性或“弱非对称性”。例如在有向无环图中，如果存在 \(x\) 可达 \(y\)，则通常不会有 \(y\) 再可达 \(x\)，除非二者实际上属于同一循环结构。
2.5 与等价关系、偏序关系的联系
当可达关系满足反身性、传递性和对称性时，它就接近等价关系的特征。此时元素可被划分为若干互相可达的类，常用于描述连通分量或状态等价类。
若可达关系同时满足反身性、传递性和反对称性，则可形成偏序关系。这样的结构常见于层次系统、依赖关系和部分排序中。由此可见，可达关系是连接等价类结构与序结构的重要桥梁。
3 图论中的可达关系
3.1 有向图中的路径可达
在有向图中，可达关系直接对应路径的存在性。若从顶点 \(u\) 到顶点 \(v\) 存在一条有向路径，则称 \(v\) 从 \(u\) 可达。这里路径可以由一个或多个边组成，因此比单纯的邻接关系更一般。
这种表达方式是图论中最基础、也最常用的形式之一。它不仅用于描述局部连接，还能反映全局结构，例如层级、环路与分量之间的关系。
3.2 节点可达与强连通
节点可达强调从某个起点出发，能到达哪些终点。若两个节点彼此都可达，则它们构成强连通关系。强连通性反映的是双向可达的整体结构，而不仅仅是单向路线。
3.2.1 可达性判定
判定节点是否可达，通常需要检查是否存在从起点到终点的路径。在小规模图中可以直接搜索，在大规模图中则常结合预处理、闭包计算或专门的数据结构。若图中存在环路，判定时还需避免重复访问，以防无限循环。
3.2.2 双向可达
双向可达指两个节点互相可达。它常被用来划分强连通分量，即把所有彼此双向可达的点归为一类。强连通分量在压缩图、程序分析和网络结构研究中都很常见，因为它能把复杂图形简化为更清晰的骨架。
3.3 路径长度与可达性
路径长度与可达性之间存在密切关系。一般来说，只要存在某条有限长度的路径，就说明终点对起点可达；而路径长度的具体数值则进一步反映了到达所需的步数或代价。
3.3.1 有限路径
可达关系只关心有限路径，不涉及无限长的转移链。若只能通过无限过程才能“逼近”某个状态，通常不被视为可达。这个限制保证了定义的稳定性，也使计算成为可能。
3.3.2 最短路径
在所有可达路径中，最短路径给出了达到目标所需的最少步数。虽然可达关系本身不要求最短性，但最短路径常用于衡量距离、代价或效率。在加权图中，这一概念还会进一步扩展为最小成本问题。
4 计算与算法
4.1 可达性问题
可达性问题是判断从给定起点是否能到达指定终点，或者从某个状态出发能否到达某一目标状态。它是图算法与形式验证中的基础问题，许多复杂任务都可归结为可达性判断。
4.2 深度优先搜索与广度优先搜索
深度优先搜索适合沿着一条路径尽可能深入，再回溯检查其他分支；广度优先搜索则按层次扩展，适合寻找最短路径或分层可达结构。二者都可用于判断可达性，只是在访问顺序和适用场景上有所不同。
4.3 Warshall 算法
Warshall 算法常用于计算有向图的传递闭包。它通过逐步引入中间顶点，判断任意两点之间是否存在经由某些中转点的路径。该算法思想简洁，尤其适合用矩阵表示图的场合。
4.4 传递闭包的计算
传递闭包的计算目标，是把“直接相连”扩展为“间接可达”。得到闭包后，任意两个点之间的可达关系都可直接查询，因此在需要大量询问的场景中非常实用。
4.4.1 矩阵方法
矩阵方法通常用邻接矩阵表示关系，再通过布尔运算或矩阵迭代求得闭包。其优点是形式统一，便于与代数方法结合；不足之处是在稠密度较低或规模较大时，可能不如遍历法直观高效。
4.4.2 图遍历方法
图遍历方法以顶点或状态为起点，分别进行搜索，记录可到达的节点集合。它实现简单，适合稀疏图和局部查询。若需要得到全局闭包，则通常要对每个顶点重复执行搜索过程。
4.5 复杂度分析
可达性计算的复杂度取决于图的规模、表示方式和所采用的算法。搜索法通常与顶点数和边数相关；矩阵法则更接近于顶点数的高次复杂度。实际应用中，往往需要在预处理成本、查询速度和存储开销之间权衡。
5 逻辑中的应用
5.1 模态逻辑中的可达关系
在模态逻辑中，可达关系用于解释不同“世界”或“状态”之间的联系。它决定了某个命题在哪些世界中成立，以及“必然”“可能”等模态词的含义。由此，可达关系成为语义解释的核心组成部分。
5.1.1 Kripke 结构中的世界可达
在 Kripke 结构中，世界之间通过可达关系连接。若从某世界可以进入另一世界，就表示后者在语义上是前者所能考虑的替代情形。这种结构广泛用于分析命题在不同情境下的成立情况。
5.1.2 必然性与可能性解释
“必然”通常表示在所有可达世界中都成立，而“可能”则表示至少存在一个可达世界使其成立。可达关系的性质会直接影响模态算子的行为，因此不同类型的可达结构会对应不同的逻辑系统。
5.2 时态逻辑中的状态演化
在时态逻辑里，可达关系常表示时间推进或状态转移。若一个状态能通过若干步到达另一个状态，就可用来刻画“未来”“过去”或“最终到达”等时间语义。它使逻辑公式能够描述动态变化过程。
5.3 形式语义中的关系解释
形式语义中，关系不仅连接对象，也连接解释层次。例如，一个表达式的意义可能依赖于某个环境能否通过规则推进到另一个环境。可达关系在这里起到桥梁作用，把结构变化与语义解释联系起来。
5.4 可达关系与证明系统
在证明系统中，可达关系常用来描述推理步骤之间的先后次序。若一个结论可以通过有限次推导从前提得到，那么前提到结论之间就可视为可达。这样的观点有助于研究证明树、归结过程和规则闭包。
6 相关概念辨析
6.1 可达关系与传递闭包
传递闭包是生成可达关系的一种标准方式。严格说来，可达关系往往就是原关系的传递闭包，或者在此基础上再加上反身性形成自反传递闭包。两者经常并用，但含义不应混淆。
6.2 可达关系与反身可达关系
反身可达关系强调对象对自身也可达，这通常对应允许零步到达的情形。若不允许零步，则应区分“可达”与“自达”。因此，在不同文献中看到相关记号时，需要先确认是否包含反身部分。
6.3 可达关系与路径关系
路径关系通常强调“存在一条具体路径”，而可达关系更强调抽象结果，即是否存在某种有限步连接。前者偏向构造性描述，后者偏向关系性结论；在很多场景中它们等价，但表述侧重点不同。
6.4 可达关系与覆盖关系
覆盖关系通常表示“直接上升一层”或“没有中间元素”的紧邻联系，常见于偏序结构。可达关系则允许经过多个中间环节，因此比覆盖关系更宽泛。覆盖关系是局部的，可达关系是整体的。
6.5 可达关系与连通性
连通性是更宏观的结构性质，关注图或系统中任意两点之间是否存在某种连接。可达关系则是有方向性的，强调从一个点能否到达另一个点。若忽略方向，连通性与可达性之间会出现关联，但两者并不等同。
7 扩展与变体
7.1 多关系系统中的可达性
在某些系统里，转移并不只由一种关系决定，而是由多个关系共同作用。此时的可达性需要考虑不同规则的组合、交替或选择。多关系系统常见于复合流程、权限模型和多层状态机。
7.2 标号转移系统中的可达关系
标号转移系统中，状态之间的转移带有标签，标签可表示动作、事件或输入。可达关系可以进一步细分为“在某类标签下可达”或“按标签序列可达”，从而支持更精细的行为分析。
7.3 概率图与随机可达性
在概率图中，边可能附带概率，表示转移发生的可能程度。此时可达性不再只是“能否到达”，还可能关心“以多大概率到达”或“在给定条件下是否存在非零概率的路径”。这使可达概念延伸到随机过程分析。
7.4 动态系统中的状态可达
动态系统研究中，状态可达性用于判断系统从初始状态是否能演化到目标状态。它既能用于离散系统，也能用于某些连续模型的离散化分析。可达集、轨迹和不变性常与这一概念配合使用。
7.5 限制条件下的可达性
在一些场景中，可达性会附加额外限制，例如步数上限、资源约束、避开某些节点或满足特定规则。此类问题比普通可达性更复杂，也更接近实际应用，因为现实中的转移往往并非完全自由。
8 典型例子
8.1 有向无环图示例
在一个有向无环图中，若存在 \(a \to b\)、\(b \to c\)、\(a \to d\)，则 \(c\) 对 \(a\) 可达，\(d\) 也对 \(a\) 可达，但通常 \(c\) 不会再回到 \(a\)。这种结构清楚体现了可达关系的方向性与层次性。
8.2 状态机示例
设某状态机包含“待机”“运行”“暂停”等状态。若“待机”可经一次启动到“运行”，“运行”可经一次暂停到“暂停”，则“待机”对“暂停”可达，尽管它们之间没有直接转移。这里的可达性反映的是操作序列，而非单条边。
8.3 关系表格示例
如果用表格记录二元关系，可以把“直接关系”填在邻接矩阵中，再通过闭包计算得到“可达关系表”。例如，原表中只标出若干直接连接，而闭包表会补充所有经由中间点可到达的项，从而完整呈现系统结构。
8.4 常见误区与反例
一个常见误区是把“没有直接边”误认为“不可达”。实际上，只要存在路径，就仍然可达。另一个误区是把“可达”理解为“彼此可达”，但后者需要双向条件，通常对应更强的结构性质。反例往往来自有向图中的单向链条：上游节点能到达下游节点，但下游节点未必能返回。