Gráfico de permutación

Gráfica que representa una permutación

El gráfico de permutación y el diagrama correspondiente para la permutación (4,3,5,1,2)

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 cuyos bordes representan pares de elementos que se invierten por la 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 puntos finales 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 (hasta la simetría de permutación ) si es primo con respecto a la descomposición modular . ^[1]

Definición y caracterización

Si es cualquier permutación de los números de a , entonces se puede definir un gráfico de permutación de en el que hay vértices , y en el que hay una arista para cualesquiera dos índices para los que aparecen antes en . Es decir, dos índices y determinan una arista 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<j}$ ${\displaystyle j}$ ${\displaystyle i}$ ${\displaystyle \rho }$ ${\displaystyle i}$ ${\displaystyle j}$

Dada una permutación , también se puede determinar un conjunto de segmentos de línea con puntos finales y , tales que . 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 lo 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 que sea 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 (k,1)}$ ${\displaystyle \sigma _{k}=i}$ ${\displaystyle y=0}$ ${\displaystyle y=1}$ ${\displaystyle \sigma }$

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

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

Algoritmos eficientes

Es posible comprobar 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 subclase de los grafos perfectos , muchos problemas que son NP-completos para grafos arbitrarios pueden resolverse de manera eficiente para grafos 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 se puede resolver en tiempo polinomial 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 del árbol y el ancho de la ruta de los gráficos 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 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 , complementos de gráficos de comparabilidad y gráficos trapezoidales .

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

Notas

1. Brandstädt, Le y Spinrad (1999), p.191.
2. Brandstädt, Le & Spinrad (1999), Proposición 4.7.1, p.57.
3. Dushnik y Miller (1941).
4. Baker, Fishburn y Roberts (1971).
5. McConnell y Spinrad (1999).
6. Golumbic (1980).
7. 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), "Ancho de árbol y ancho de camino de los gráficos 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), Clases de grafos: un estudio , Monografías SIAM sobre matemáticas discretas y aplicaciones, 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", Discrete Mathematics , 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), "Gráficos de permutación bipartitos", Discrete Applied Mathematics , 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 grafos y sus inclusiones
• Weisstein, Eric W. , "Gráfico de permutación", MathWorld