构造一个置换图

Question

我已阅读了关于置换图如何使许多NP完全问题更容易解决的问题。例如最大集团问题，树宽问题等。但是，我无法理解从给定图G（V，E）创建置换图的过程。如何去做这件事？

Answer 1

您不会从图形创建置换图，而是从置换创建。该过程非常简单：

1. 写入编号1〜一行n，则
2. 根据它们出现在您的排列顺序再次写入它们在单独的，平行线;
3. 将第一行中的每个元素连接到第二行上的相同元素（1到1,2到2，...，n到n），
4. 将每个这样的连接标记为它连接的数字例如连接2到2接收标签2）;
5. 得到的置换图是通过将每个连接视为顶点并在相应的连接相交时连接两个顶点来获得的。

如果还不清楚，see the nice example on Wikipedia。

从这个过程可以清楚地看出，这样一个图可以始终由任何置换构成;但是，有一个置换图可能会导致您推断与其相对应的几个置换。