Gráfico de permutación - Permutation graph

Diagrama de correspondencia para la permutación (4,3,5,1,2), debajo de su gráfico de permutación correspondiente

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 .

Definición y caracterización

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

Dada una permutación , también se puede determinar un conjunto de segmentos de línea con puntos finales y . Los puntos finales de estos segmentos se encuentran en las dos líneas paralelas y , 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, el gráfico de permutación de coincide con el gráfico 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. ${\ Displaystyle \ sigma}$ ${\ Displaystyle s_ {i}}$ ${\ Displaystyle (i, 0)}$ ${\ Displaystyle (\ sigma _ {i}, 1)}$ ${\ Displaystyle y = 0}$ ${\ Displaystyle y = 1}$ ${\ Displaystyle \ sigma}$

Los gráficos de permutación tienen otras caracterizaciones equivalentes:

Una gráfica es una gráfica de permutación si y solo si es una gráfica circular que admite un ecuador, es decir, una cuerda adicional que se cruza con todas las demás cuerdas. ${\ Displaystyle G}$ ${\ Displaystyle G}$
Un gráfico es un gráfico de permutación si y solo si ambos y su complemento son gráficos de comparabilidad . ${\ Displaystyle G}$ ${\ Displaystyle G}$ ${\ Displaystyle {\ overline {G}}}$
Un gráfico 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. ${\ Displaystyle G}$
Si una gráfica es una gráfica de permutación, también lo es su complemento. Se puede obtener una permutación que representa el complemento de invirtiendo la permutación que representa . ${\ Displaystyle G}$ ${\ Displaystyle G}$ ${\ Displaystyle 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 .

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.
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.

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

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.

Languages

In other projects