En teoría de grafos , un menor superficial o un menor de profundidad limitada es una forma restringida de un menor de grafos en la que los subgrafos que se contraen para formar el menor tienen un diámetro pequeño . Los menores superficiales fueron introducidos por Plotkin, Rao y Smith (1994), quienes atribuyeron su invención a Charles E. Leiserson y Sivan Toledo. [1]
Una forma de definir un menor de un grafo no dirigido G es especificando un subgrafo H de G , y una colección de subconjuntos disjuntos S i de los vértices de G , cada uno de los cuales forma un subgrafo inducido conexo H i de H . El menor tiene un vértice v i para cada subconjunto S i , y una arista v i v j siempre que exista una arista de S i a S j que pertenezca a H .
En esta formulación, un menor d -superficial (alternativamente llamado un menor superficial de profundidad d ) es un menor que se puede definir de tal manera que cada uno de los subgrafos H i tiene un radio de como máximo d , lo que significa que contiene un vértice central c i que está dentro de la distancia d de todos los demás vértices de H i . Nótese que esta distancia se mide por el conteo de saltos en H i y , debido a eso, puede ser mayor que la distancia en G. [1]
Los menores poco profundos de profundidad cero son lo mismo que los subgrafos del grafo dado. Para valores suficientemente grandes de d (incluidos todos los valores al menos tan grandes como el número de vértices), los menores d -poco profundos de un grafo dado coinciden con todos sus menores. [1]
Nešetřil y Ossona de Mendez (2012) utilizan menores superficiales para dividir las familias de grafos finitos en dos tipos. Dicen que una familia de grafos F es densa en algún lugar si existe un valor finito de d para el cual los d -menores superficiales de grafos en F consisten en cada grafo finito. De lo contrario, dicen que una familia de grafos es densa en ningún lugar . [2] Esta terminología se justifica por el hecho de que, si F es una clase de grafos densa en ningún lugar, entonces (para cada ε > 0) los grafos de n -vértices en F tienen O ( n 1 + ε ) aristas; por lo tanto, los grafos densos en ningún lugar son grafos dispersos . [3]
Un tipo más restrictivo de familia de grafos, descrito de manera similar, son las familias de grafos de expansión acotada . Se trata de familias de grafos para las que existe una función f tal que la relación entre aristas y vértices en cada d -menor superficial es como máximo f ( d ). [4] Si esta función existe y está acotada por un polinomio , se dice que la familia de grafos tiene expansión polinómica.
Como demostraron Plotkin, Rao y Smith (1994), los grafos con menores superficiales excluidos se pueden particionar de manera análoga al teorema del separador planar para grafos planares . En particular, si el grafo completo K h no es un menor d -superficial de un grafo de n -vértices G , entonces existe un subconjunto S de G , con tamaño O ( dh 2 log n + n / d ), tal que cada componente conexo de G \ S tiene como máximo 2 n /3 vértices. El resultado es constructivo: existe un algoritmo de tiempo polinomial que encuentra dicho separador o un menor d -superficial K h . [5] Como consecuencia, demostraron que cada familia de grafos cerrada con menores obedece a un teorema del separador casi tan fuerte como el de los grafos planares.
Plotkin et al. también aplicaron este resultado a la partición de mallas del método de elementos finitos en dimensiones superiores; para esta generalización, son necesarios menores poco profundos, ya que (sin restricción de profundidad) la familia de mallas en tres o más dimensiones tiene todos los grafos como menores. Teng (1998) extiende estos resultados a una clase más amplia de grafos de alta dimensión.
De manera más general, una familia de grafos hereditarios tiene un teorema de separador donde el tamaño del separador es una potencia sublineal de n si y solo si tiene expansión polinomial. [6]