Implication Graph

定义 Definition

Implication graph（蕴含图/推导图）：在逻辑与计算机科学中，用有向图表示“如果……则……”的蕴含关系。常见于命题逻辑与可满足性问题（SAT，尤其是 2-SAT）：把文字（如 \(x\)、\(\lnot x\)）作为节点，用边 \(a \rightarrow b\) 表示“若 \(a\) 为真，则 \(b\) 必为真”。

发音 Pronunciation

/mplken rf/

例句 Examples

An implication graph helps visualize logical constraints in a 2-SAT problem.
蕴含图有助于把 2-SAT 问题中的逻辑约束直观地画出来。

By analyzing strongly connected components in the implication graph, we can determine whether the formula is satisfiable and even construct a valid assignment.
通过分析蕴含图中的强连通分量，我们可以判断公式是否可满足，甚至构造出一个满足条件的赋值方案。

词源 Etymology

implication 源自拉丁语 implicare，意为“缠绕、牵连”，引申为“推出、蕴含”；graph 源自希腊语 graphein，意为“书写、描画”，在数学与计算机中指“图（由点和边构成的结构）”。合起来即“表示蕴含关系的图”。

相关词 Related Words

• Directed Graph
• Implication
• 2-SAT
• SAT
• Literal
• Clause
• Strongly Connected Component
• Constraint

文学与经典作品 Literary Works

• Introduction to Algorithms（CLRS，《算法导论》）：在讨论图算法与可满足性相关内容时常提到用图来表达逻辑约束的思路（与 2-SAT 的蕴含图方法相关）。
• Algorithm Design（Kleinberg & Tardos，《算法设计》）：讲解 2-SAT 等问题时常使用“implication graph”作为核心建模工具。
• Algorithms（Dasgupta, Papadimitriou & Vazirani，《算法》）：在可满足性与图模型的教学语境中常出现蕴含图及其判定技巧。