Grafo de permutación

En el campo matemático de la teoría de grafos , un grafo de permutación es un grafo cuyos vértices representan los elementos de una permutación y cuyas aristas representan pares de elementos invertidos por dicha permutación. Los grafos de permutación también pueden definirse geométricamente como los grafos de intersección de segmentos de línea cuyos extremos se encuentran en dos líneas paralelas . Diferentes permutaciones pueden dar lugar al mismo grafo de permutación; un grafo dado tiene una representación única (salvo simetría de permutación ) si es primo con respecto a la descomposición modular . ^{[ 1 ]}

Si${\displaystyle \rho =(\sigma _{1},\sigma _{2},...,\sigma _{n})}$es cualquier permutación de los números de${\displaystyle 1}$a${\displaystyle n}$, entonces se puede definir un grafo de permutación a partir de${\displaystyle \sigma }$en los que hay${\displaystyle n}$vértices${\displaystyle v_{1},v_{2},...,v_{n}}$y en la que hay un borde${\displaystyle v_{i}v_{j}}$para cualesquiera dos índices${\displaystyle i<j}$para qué${\displaystyle j}$aparece antes${\displaystyle i}$en${\displaystyle \rho }$. Es decir, dos índices${\displaystyle i}$y${\displaystyle j}$determinan una arista en el grafo de permutación exactamente cuando determinan una inversión en la permutación.

Dada una permutación${\displaystyle \sigma }$, también se puede determinar un conjunto de segmentos de línea${\displaystyle s_{i}}$con puntos finales${\displaystyle (i,0)}$y${\displaystyle (k,1)}$, de tal manera que${\displaystyle \sigma _{k}=i}$Los extremos de estos segmentos se encuentran sobre las dos líneas paralelas.${\displaystyle y=0}$y${\displaystyle y=1}$y dos segmentos tienen una intersección no vacía si y solo si corresponden a una inversión en la permutación. Por lo tanto, el grafo de permutación de${\displaystyle \sigma }$coincide con el grafo de intersección de los segmentos. Para cada par de líneas paralelas y cada conjunto finito de segmentos de línea con extremos en ambas líneas, el grafo de intersección de los segmentos es un grafo de permutación; en el caso de que los extremos de los segmentos sean todos distintos, una permutación para la cual es el grafo de permutación puede obtenerse numerando los segmentos en una de las dos líneas en orden consecutivo y leyendo estos números en el orden en que aparecen los extremos de los segmentos en la otra línea.

Los grafos de permutación tienen otras caracterizaciones equivalentes:

• Un gráfico${\displaystyle G}$es un grafo de permutación si y solo si${\displaystyle G}$es un gráfico circular que admite un ecuador , es decir, una cuerda adicional que interseca a todas las demás cuerdas. ^{[ 2 ]}
• Un gráfico${\displaystyle G}$es un grafo de permutación si y solo si ambos${\displaystyle G}$y su complemento${\displaystyle {\overline {G}}}$son gráficos de comparabilidad . ^{[ 3 ]}
• Un gráfico${\displaystyle G}$es un grafo de permutación si y solo si es el grafo de comparabilidad de un conjunto parcialmente ordenado que tiene dimensión de orden como máximo dos. ^{[ 4 ]}
• Si un gráfico${\displaystyle G}$es un grafo de permutación, por lo que también lo es su complemento. Una permutación que representa el complemento de${\displaystyle G}$se puede obtener invirtiendo la permutación que representa${\displaystyle G}$.

Es posible comprobar si un grafo dado es un grafo de permutación y, en caso afirmativo, construir una permutación que lo represente en tiempo lineal . ^{[ 5 ]}

Como subclase de los grafos perfectos , muchos problemas que son NP-completos para grafos arbitrarios pueden resolverse eficientemente para grafos de permutación. Por ejemplo:

• La camarilla más grande en un grafo de permutación corresponde a la subsecuencia decreciente más larga en la permutación que define el grafo, por lo que el problema de la camarilla puede resolverse en tiempo polinomial para grafos de permutación utilizando un algoritmo de subsecuencia decreciente más larga. ^{[ 6 ]}
• De igual modo, una subsecuencia creciente en una permutación corresponde a un conjunto independiente del mismo tamaño en el grafo de permutación correspondiente.
• El ancho de árbol y el ancho de camino de los grafos de permutación se pueden calcular en tiempo polinomial; estos algoritmos explotan el hecho de que el número de separadores de vértices mínimos de inclusión en un grafo de permutación es polinomial en el tamaño del grafo. ^{[ 7 ]}

Los grafos de permutación son un caso especial de grafos circulares , grafos de comparabilidad , complementos de grafos de comparabilidad y grafos trapezoidales .

Las subclases de los grafos de permutación incluyen los grafos de permutación bipartitos (caracterizados por Spinrad, Brandstädt y Stewart 1987 ) y los cografos .

• Baker, Kirby A.; Fishburn, Peter C .; Roberts, Fred S. (1971), "Órdenes parciales de dimensión 2", Networks , 2 (1): 11– 28, doi : 10.1002/net.3230020103.
• Bodlaender, Hans L.; Kloks, Ton; Kratsch, Dieter (1995), "Ancho de árbol y ancho de camino de grafos de permutación", SIAM Journal on Discrete Mathematics , 8 (4): 606–616 , doi : 10.1137/S089548019223992X , hdl : 1874/16657.
• Brandstädt, Andreas ; Le, Van Bang; Spinrad, Jeremy P. (1999), Graph Classes: A Survey , SIAM Monographs on Discrete Mathematics and Applications, ISBN 0-89871-432-X.
• Dushnik, Ben; Miller, Edwin W. (1941), "Conjuntos parcialmente ordenados", American Journal of Mathematics , 63 (3): 600– 610, doi : 10.2307/2371374 , JSTOR 2371374 .
• Golumbic, Martin C. (1980), Teoría algorítmica de grafos y grafos perfectos , Ciencias de la Computación y Matemáticas Aplicadas, Academic Press, pág.  159.
• McConnell, Ross M.; Spinrad, Jeremy P. (1999), "Descomposición modular y orientación transitiva", Matemáticas Discretas , 201 ( 1–3 ): 189–241 , doi : 10.1016/S0012-365X(98)00319-7 , MR 1687819 .
• Spinrad, Jeremy P.; Brandstädt, Andreas ; Stewart, Lorna K. (1987), "Grafos de permutación bipartitos", Matemáticas Aplicadas Discretas , 18 (3): 279– 292, doi : 10.1016/s0166-218x(87)80003-3.

• "Grafo de permutación" , Sistema de información sobre clases de grafos y sus inclusiones
• Weisstein, Eric W. , "Grafo de permutación" , MathWorld