Вы не можете создать граф перестановок из графика, но из перестановки. Процесс довольно прост:
- номера записи 1 до п на линии, то
- записать их снова на отдельной параллельной линии в соответствии с порядком, в котором они появляются в вашей перестановки;
- подключить каждый элемент от первой строки к тому же элементу на второй строке (от 1 до 1, от 2 до 2, ..., от n до n),
- отметьте каждое такое соединение с номерами, которые он соединяет (например, соединение 2 - 2 принимает метку 2);
- полученный граф перестановки получается путем обработки каждого соединения в виде вершины и соединения двух вершин всякий раз, когда соответствующие соединения пересекаются.
Если это еще не ясно, see the nice example on Wikipedia.
Из процесса ясно, что такой график всегда можно построить из любой перестановки; однако, наличие перестановочного графа может привести к выведению нескольких перестановок, соответствующих ему.
Я думаю, вы немного ошибаетесь. Пермутационные графики - это конкретный экземпляр графов, которые некоторые проблемы, которые * обычно * NP-Hard, решаются специально на этих графах эффективно - подобно [двучастному графу] (http://en.wikipedia.org/wiki/ Bipartite_graph) [Хотя это разные графы, конечно]. Не каждый граф является перестановочным графом. И маловероятно, что вы можете полиномиально преобразовать любой граф в график перестановок - это сделает P = NP. – amit
@amit вы должны написать это как ответ – alestanis