原书出处
Introduction to Algorithms, Fourth Edition
34 第34章 NP完全性
[u, v, 1], [u, v, 6], [v, u, 1], and [v, u, 6] will have edges incident from outside Γuv.
Any hamiltonian cycle of G′ must traverse the edges of Γuv in one of the three ways shown in Figures 34.16(b)–(d). If the cycle enters through vertex [u, v, 1], it must exit through vertex [u, v, 6], and it either visits all 12 of the gadget’s vertices (Figure 34.16(b)) or the six vertices [u, v, 1] through [u, v, 6] (Figure 34.16(c)). In the latter case, the cycle will have to reenter the gadget to visit vertices [v, u, 1] through [v, u, 6].
Similarly, if the cycle enters through vertex [v, u, 1], it must exit through vertex [v,
原书定位详情
来源:a19c7933-4eda-4176-aebd-30fe7e1ad292
正文位置:extracted/Introduction to Algorithms, Fourth Edition/_epub-src/OEBPS/chapter034.xhtml
EPUB SHA-256:ec7ced04bb875b93983816aef7a667855a4b71c5cf53b63406b9439c74e27aea