知识卡片
组合电路的依赖图无环
组合电路由逻辑门和导线组成,门输出可供多个门输入使用;导线只能有一个产生它的门输出。
把门当顶点、依赖当有向边,图必须无环,否则不再是此处讨论的组合电路。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第34章 NP完全性 · 查看原书依据
Boolean combinational circuits contain no cycles. In other words, for a given combinational circuit, imagine a directed graph G = (V, E) with one vertex for each combinational element and with k directed edges for each wire whose fan-out is k, where the graph contains a directed edge (u, v) if a wire connects the output of element u to an input of element v. Then G must be acyclic. A truth assignment for a boolean combinational circuit is a set of
参考来源
- 位置:《算法导论(第4版)》第34章《NP完全性》(OEBPS/chapter034.xhtml,文本字符[50000,55000))。
- 结论依据:原文§34.2–34.3的复杂度类别、正式归约与电路可满足性;图表或XHTML已核对。
- 原始内容:Boolean combinational circuits contain no cycles. In other words, for a given combinational circuit, imagine a directed graph G = ( V , E ) with one vertex for each combinational element and with k directed edges for each wire whose fan-out is k , where the graph contains a directed edge ( u , v ) if a wire connects the output of element u to an input of element v . Then G must be acyclic. A truth assignment for a boolean combinational circuit is a set of