强连通分量各仅含一条外部入边是否为可约图的充要条件？

结论：该条件是图为可约图的充分条件，但并非必要条件 #

充分性验证

若图中每个强连通分量（SCC）仅存在一条来自分量外部的入边，可从根SCC（无外部入边的分量）出发，按依赖顺序逐步约简每个SCC：由于每个非根SCC只有唯一外部入口，可将该入口作为分量代表，逐步合并分量内节点，最终将整个图简化为单点，完全符合可约图的定义。

必要性不成立的反例

存在可约图，其中某个SCC拥有多条外部入边，但仍满足可约性。例如：

• 根SCC包含两个节点a1和a2，两者均指向非根SCC中的节点b1；
• 此时非根SCC有两条外部入边，但整个图的控制流可通过支配关系（a1和a2的共同支配节点为根SCC入口）完成约简，不存在不可约循环，因此属于可约图。

相关参考文献 #

• 《Advanced Compiler Design and Implementation》（Steven Muchnik）：第7章「Control-Flow Analysis」系统阐述了可约流图的定义、等价特征及验证方法，明确了可约图与支配树、循环结构的关联。
• 《Compilers: Principles, Techniques, and Tools》（Aho, Sethi, Ullman）：第9章「Machine-Independent Optimizations」说明可约流图的充要条件，核心是不存在「不可约循环」（无法通过节点消去简化的循环结构）。
• 《Program Flow Analysis: Theory and Applications》（Neil D. Jones 等）：深入探讨程序流图的可约性理论，包含SCC分层与可约性的详细推导。

内容的提问来源于stack exchange，提问作者Etten Moor