知识卡片

普通读书笔记卡 · 3714.b.3.a

组合电路的依赖图无环

理解等级:中级

组合电路由逻辑门和导线组成,门输出可供多个门输入使用;导线只能有一个产生它的门输出。

把门当顶点、依赖当有向边,图必须无环,否则不再是此处讨论的组合电路。

这张卡片看不懂?

已有反馈 · 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