我正在阅读 Andrew B. Kahng、Jens Lienig、Igor L. Markov 和 Jin Hu 所著的《VLSI Physical Design: From Graph Partitioning to Timing Closure》一书。
在那本书中，有一个组合电路的图片，如图 1 所示。
对于图 1 中的组合电路，作者展示了如下图 2 所示的连接图。
我的问题是，门 x 和 y 之间没有直接连接。在那种情况下，为什么图表会显示门（或节点） x 和 y 之间的两条边？
谢谢你的帮助。
虽然 x 和 y 之间没有直接连接（例如 x 馈送 y），但网络 N1 连接了三个节点：a、x 和 y。因此，由于所有三个在电气上是等效的，因此您必须保留所有三个节点之间关系的连接。因此，对于 N1，您需要 a 和 x 之间的一条边，a 和 y 之间的一条边，以及 x 和 y 之间的一条边。同样对于 N2，当它连接 b、x 和 y 时，您需要在 b、x 和 y 之间的每个引脚对之间有一条边。
在一般情况下，如果您有一个多引脚网络，一个连接多个节点的网络，那么您需要在每个引脚对之间有一条边：
“一个 p-pin 网络由（p 选择 2）其节点之间的总连接表示”——第 28 页的连接图定义。
顺便说一句，您可以看到这是一个乏味的过程，并且在此模型中边的数量会迅速增长。但是，如果您使用超边和超图模型，那么您只需要一个超边来表示 N1 和一个超边来表示 N2（相对于三个常规边）。
我还想指出，这个连通性定义非常笼统，在某些情况下，可以删除 x 和 y 之间的边。例如，如果您在 N1 上执行时序传播（例如，到达时间），那么您只需要 a 和 x 之间的有向边以及 a 和 y 之间的有向边。
我希望这有帮助。