En matemáticas , un gráfico de permutación es un gráfico cuyos vértices representan los elementos de una permutación y cuyas aristas representan pares de elementos que son invertidos por la permutación . Los gráficos de permutación también se pueden definir geométricamente, como los gráficos de intersección de segmentos de línea cuyos puntos finales se encuentran en dos líneas paralelas . Diferentes permutaciones pueden dar lugar al mismo gráfico de permutación; un gráfico dado tiene una representación única (hasta la simetría de permutación) si es primo con respecto a la descomposición modular . [1]
Definición y caracterización
Si σ = (σ 1 , sigma 2 , ..., σ n ) es cualquier permutación de los números de 1 a n , entonces uno puede definir un gráfico de permutación de σ en el que hay n vértices v 1 , v 2 ,. .., v n , y en el que hay una arista v i v j para dos índices cualesquiera i y j para los cuales i < j y σ i > σ j . Es decir, dos índices i y j determinar un borde en el gráfico de permutación exactamente cuando determinan una inversión en la permutación.
Dada una permutación σ, también se puede determinar un conjunto de segmentos de línea s i con puntos finales ( i , 0) y (σ i , 1). Los puntos finales de estos segmentos se encuentran en las dos líneas paralelas y = 0 e 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 tanto, la gráfica de permutación de σ coincide con la gráfica de intersección de los segmentos. Para cada dos líneas paralelas y cada conjunto finito de segmentos de línea con puntos finales en ambas líneas, el gráfico de intersección de los segmentos es un gráfico de permutación; En el caso de que los puntos finales del segmento sean todos distintos, se puede dar una permutación para la cual es el gráfico de permutación 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 puntos finales del segmento. en la otra línea.
Los gráficos de permutación tienen otras caracterizaciones equivalentes:
- Una gráfica G es una gráfica de permutación si y solo si G es una gráfica circular que admite un ecuador, es decir, una cuerda adicional que se cruza con todas las demás cuerdas. [2]
- Un gráfico G es un gráfico de permutación si y solo si tanto G como su complemento son gráficos de comparabilidad . [3]
- Un gráfico G es un gráfico de permutación si y solo si es el gráfico de comparabilidad de un conjunto parcialmente ordenado que tiene una dimensión de orden como máximo dos. [4]
- Si un gráfico G es un gráfico de permutación, también lo es su complemento. Una permutación que representa el complemento de G puede obtenerse mediante la inversión de la permutación que representa G .
Algoritmos eficientes
Es posible probar si un gráfico dado es un gráfico de permutación y, de ser así, construir una permutación que lo represente, en tiempo lineal . [5]
Como una subclase de las gráficas perfectas , muchos problemas que son NP-completos para gráficas arbitrarias pueden resolverse eficientemente para gráficas de permutación. Por ejemplo:
- la camarilla más grande en un gráfico de permutación corresponde a la subsecuencia decreciente más larga en la permutación que define el gráfico, por lo que el problema de la camarilla puede resolverse en tiempo polinómico para gráficos de permutación utilizando un algoritmo de subsecuencia decreciente más larga. [6]
- del mismo modo, una subsecuencia creciente en una permutación corresponde a un conjunto independiente del mismo tamaño en el gráfico de permutación correspondiente.
- el ancho de árbol y el ancho de ruta de los gráficos de permutación se pueden calcular en tiempo polinomial; estos algoritmos aprovechan el hecho de que el número de separadores de vértices mínimos de inclusión en un gráfico de permutación es polinomial en el tamaño del gráfico. [7]
Relación con otras clases de gráficos
Los gráficos de permutación son un caso especial de gráficos circulares , gráficos de comparabilidad , los complementos de gráficos de comparabilidad y gráficos trapezoidales .
Las subclases de las gráficas de permutación incluyen las gráficas de permutación bipartitas (caracterizadas por Spinrad, Brandstädt & Stewart 1987 ) y las cografías .
Notas
- ^ Brandstädt, Le y Spinrad (1999) , p.191.
- ^ Brandstädt, Le & Spinrad (1999) , Proposición 4.7.1, p.57.
- ^ Dushnik y Miller (1941) .
- ^ Baker, Fishburn y Roberts (1971) .
- ^ McConnell y Spinrad (1999) .
- ^ Golumbic (1980) .
- ^ Bodlaender, Kloks y Kratsch (1995)
Referencias
- 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), "Treewidth and pathwidth of permutation graphs", 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" (PDF) , American Journal of Mathematics , 63 (3): 600–610, doi : 10.2307 / 2371374 , JSTOR 2371374.
- Golumbic, Martin C. (1980), Teoría algorítmica de gráficos y gráficos perfectos , Ciencias de la computación y matemáticas aplicadas, Academic Press, p. 159.
- McConnell, Ross M .; Spinrad, Jeremy P. (2011), "Descomposición modular y orientación transitiva", Matemáticas discretas , 201 (1–3): 189–241, arXiv : 1010.5447 , doi : 10.1016 / S0012-365X (98) 00319-7 , MR 1687819.
- Spinrad, Jeremy P .; Brandstädt, Andreas ; Stewart, Lorna K. (1987), "Gráficos de permutación bipartita", Matemáticas aplicadas discretas , 18 (3): 279-292, doi : 10.1016 / s0166-218x (87) 80003-3.
enlaces externos
- "Gráfico de permutación" , Sistema de información sobre clases de gráficos y sus inclusiones
- Weisstein, Eric W. "Gráfico de permutación" . MathWorld .