Ancho de tallado

En la teoría de grafos , el ancho de corte de un grafo es un número, definido a partir del propio grafo, que describe la cantidad de aristas que separan los clústeres en una agrupación jerárquica de los vértices del grafo.

El ancho de un tallado se define en términos de agrupaciones jerárquicas de los vértices de un grafo dado, denominadas "tallados". Un tallado puede describirse como un árbol binario sin raíz cuyas hojas están etiquetadas con los vértices del grafo dado. Al eliminar cualquier arista de este árbol, este se divide en dos subárboles y, correspondientemente, sus vértices se dividen en dos clústeres. Los clústeres de vértices formados de esta manera constituyen una familia de conjuntos laminares : cualesquiera dos clústeres de vértices (no solo los dos clústeres complementarios formados al eliminar la misma arista) son disjuntos o uno está contenido en el otro. El ancho de un tallado, definido de esta manera, es el número máximo de aristas que conectan dos clústeres complementarios. El ancho de un tallado del grafo es el ancho mínimo de cualquier agrupación jerárquica. ^{[ 1 ]}

Los grafos de ancho de tallado uno son exactamente los emparejamientos . Los grafos de ancho de tallado dos son exactamente aquellos formados a partir de uniones disjuntas de grafos de caminos y grafos de ciclos . Los grafos de ancho de tallado tres son los 2-árboles parciales subcúbicos. Esto significa que su grado máximo es tres y que son subgrafos de grafos serie-paralelo . Todos los demás grafos tienen un ancho de tallado de al menos cuatro. ^{[ 2 ]}

El ancho de tallado es NP-difícil en general, pero puede calcularse en tiempo polinomial en grafos planares . ^{[ 1 ]} Puede aproximarse dentro de una constante de la misma razón de aproximación que los cortes equilibrados , ^{[ 3 ]} para los cuales la mejor razón de aproximación actual es${\displaystyle O({\sqrt {\log n}})}$. ^{[ 4 ]} También es tratable con parámetros fijos : para cualquier fijo${\displaystyle k}$, probando si el ancho de tallado es como máximo${\displaystyle k}$y, de ser así, encontrar una agrupación jerárquica que realice ese ancho, se puede realizar en tiempo lineal . ^{[ 5 ]} En general, calcular el ancho de tallado exactamente, en un multigrafo con${\displaystyle n}$vértices y${\displaystyle m}$bordes, puede hacerse a tiempo${\displaystyle O(2^{n}n^{3}\log n\log \log n\log m)}$. ^{[ 6 ]}

El ancho de tallado es solo uno de los varios parámetros de ancho de grafo que miden cuán arbóreo es un grafo dado. Otros incluyen el ancho de árbol y el ancho de rama . El ancho de rama de un grafo se define de manera similar al ancho de tallado, utilizando agrupamientos jerárquicos, pero de las aristas de un grafo en lugar de sus vértices; estos se denominan descomposiciones de rama . Un tallado de un grafo se puede convertir en una descomposición de rama adjuntando cada arista del grafo a uno de sus dos extremos y expandiendo cada hoja de un tallado en un subárbol que representa sus aristas adjuntas. Usando esta construcción, se puede demostrar que para cualquier grafo, el ancho de tallado es mayor o igual que la mitad del ancho de rama, y ​​es menor o igual que el grado multiplicado por el ancho de rama. Dado que el ancho de árbol y el ancho de rama siempre están dentro de factores constantes entre sí, se pueden usar límites similares para relacionar el ancho de tallado con el ancho de árbol. ^{[ 7 ]}

Otro parámetro de anchura, definido por el número de aristas que abarcan cortes en un grafo, es su anchura de corte , definida mediante un ordenamiento lineal de los vértices del grafo y el sistema de particiones que separa los vértices anteriores de los posteriores en dicho ordenamiento. ^{[ 5 ]} A diferencia de la anchura de tallado, este sistema de particiones no incluye una partición que separe cada vértice de los demás, por lo que (a pesar de utilizar una clase más restringida de familias de cortes) la anchura de corte puede ser menor que la anchura de tallado. Sin embargo, la anchura de tallado siempre es, como máximo, el máximo entre la anchura de corte y el grado máximo del grafo. ^{[ 7 ]}