LISTA DE PROBLEMAS

Número de pendiente

De Wikipedia, la enciclopedia libre

Saltar a navegaciónSaltar a búsqueda

Un dibujo del gráfico de Petersen con pendiente número 3

En el dibujo de gráficos y la teoría de gráficos geométricos , el número de pendiente de un gráfico es el número mínimo posible de pendientes distintas de bordes en un dibujo del gráfico en el que los vértices se representan como puntos en el plano euclidiano y los bordes se representan como segmentos de línea que No pasar por ningún vértice no incidente.

Gráficos completos [ editar ]

Aunque anteriormente se habían estudiado problemas estrechamente relacionados en geometría discreta , por ejemplo, Scott (1970) y Jamison (1984) , el problema de determinar el número de pendiente de un gráfico fue introducido por Wade y Chu (1994) , quienes mostraron que el número de pendiente de un n -vertex gráfico completo K _n es exactamente  n . Se puede formar un dibujo con este número de pendiente colocando los vértices del gráfico en un polígono regular .

Relación con el grado [ editar ]

El número de pendiente de una gráfica de grado máximo d es claramente al menos$${\ displaystyle \ lceil d / 2 \ rceil}, porque como máximo dos de los bordes incidentes en un vértice de grado d pueden compartir una pendiente. Más precisamente, el número de pendiente es al menos igual a la arboricidad lineal del gráfico, ya que los bordes de una sola pendiente deben formar un bosque lineal , y la arboricidad lineal a su vez es al menos$${\ displaystyle \ lceil d / 2 \ rceil}.

Problema no resuelto en matemáticas : ¿Las gráficas de grado máximo cuatro tienen un número de pendiente acotada? (Más problemas no resueltos en matemáticas)

Existen gráficos con un grado máximo de cinco que tienen un número de pendiente arbitrariamente grande. ^[1] Sin embargo, cada gráfica de grado máximo tres tiene un número de pendiente como máximo cuatro; ^[2] el resultado de Wade & Chu (1994) para el gráfico completo K ₄ muestra que esto es estricto. No todos los conjuntos de cuatro pendientes son adecuados para dibujar todos los gráficos de grado 3: un conjunto de pendientes es adecuado para este propósito si y solo forma las pendientes de los lados y diagonales de un paralelogramo . En particular, cualquier gráfico de grado 3 se puede dibujar de modo que sus bordes sean paralelos a los ejes o paralelos a las diagonales principales de la red de enteros . ^[3]No se sabe si las gráficas de grado máximo cuatro tienen un número de pendiente acotado o no acotado. ^[4]

El método de Keszegh, Pach y Pálvölgyi (2011) para combinar empaques circulares y cuadrúpedos para lograr un número de pendiente acotado para gráficos planos con grado acotado

Gráficos planos [ editar ]

Como mostraron Keszegh, Pach y Pálvölgyi (2011) , cada gráfico plano tiene un dibujo de línea recta plano en el que el número de pendientes distintas es una función del grado del gráfico. Su prueba sigue una construcción de Malitz y Papakostas (1994) para delimitar la resolución angular de los gráficos planos en función del grado, completando el gráfico en un gráfico plano máximo sin aumentar su grado en más de un factor constante, y aplicando el círculo teorema de embalajepara representar este gráfico aumentado como una colección de círculos tangentes. Si el grado del gráfico inicial está acotado, la relación entre los radios de los círculos adyacentes en el empaque también estará acotada, ^{[5] lo} que a su vez implica que el uso de un quadtree para colocar cada vértice del gráfico en un punto dentro de su círculo producirá pendientes que son proporciones de enteros pequeños. El número de pendientes distintas producidas por esta construcción es exponencial en el grado del gráfico.

Complejidad [ editar ]

Es NP-complete para determinar si un gráfico tiene pendiente número dos. ^[6] De esto, se deduce que es NP-difícil determinar el número de pendiente de un gráfico arbitrario, o aproximarlo con una relación de aproximación mejor que 3/2.

También es NP completo para determinar si un gráfico plano tiene un dibujo plano con pendiente número dos, ^[7] y es difícil para la teoría existencial de los reales determinar el número mínimo de pendiente de un dibujo plano.

En la teoría de gráficos , el ancho de árbol de un gráfico no dirigido es un número asociado con el gráfico. El ancho de árbol se puede definir de varias maneras equivalentes: desde el tamaño del vértice más grande establecido en la descomposición de un árbol del gráfico, desde el tamaño de la camarilla más grande en una terminación cordal del gráfico, desde el orden máximo de un refugio que describe una estrategia para un juego de persecución y evasión en el gráfico, o del orden máximo de una zarza , una colección de subgrafías conectadas que se tocan entre sí.

El ancho de árbol se usa comúnmente como parámetro en el análisis de complejidad parametrizado de algoritmos gráficos . Los gráficos con treewidth en la mayoría de k también se llaman parciales k -Los árboles ; muchas otras familias gráficas bien estudiadas también tienen un ancho de árbol acotado.

El concepto de ancho de árbol fue introducido originalmente por Umberto Bertelé y Francesco Brioschi ( 1972 ) bajo el nombre de dimensión . Más tarde fue redescubierto por Rudolf Halin  ( 1976 ), basado en propiedades que comparte con un parámetro gráfico diferente, el número de Hadwiger . Más tarde fue redescubierto nuevamente por Neil Robertson y Paul Seymour  ( 1984 ) y desde entonces ha sido estudiado por muchos otros autores.

Definición [ editar ]

Un gráfico con ocho vértices y una descomposición del árbol en un árbol con seis nodos. Cada borde del gráfico conecta dos vértices que se enumeran juntos en algún nodo del árbol, y cada vértice del gráfico se enumera en los nodos de un subárbol contiguo del árbol. Cada nodo de árbol enumera como máximo tres vértices, por lo que el ancho de esta descomposición es dos.

La descomposición de un árbol de un gráfico G = ( V , E ) es un árbol, T , con nodos X ₁ , ..., X _n , donde cada X _i es un subconjunto de V , que satisface las siguientes propiedades ^[2] (el El término nodo se usa para referirse a un vértice de T para evitar confusión con los vértices de G ):

1. La unión de todos los conjuntos X _i es igual a V . Es decir, cada vértice de gráfico está contenido en al menos un nodo de árbol.
2. Si X _i y X _j contienen un vértice v , entonces todos los nodos X _k de T en la ruta (única) entre X _i y X _{j también} contienen v . De manera equivalente, los nodos del árbol contienen vértice v forman un subárbol conectado de T .
3. Para cada borde ( v , w ) en el gráfico, hay un subconjunto X _i que contiene v y w . Es decir, los vértices son adyacentes en el gráfico solo cuando los subárboles correspondientes tienen un nodo en común.

El ancho de la descomposición de un árbol es el tamaño de su conjunto más grande X _i menos uno. El treewidth tw ( G ) de un gráfico G es la anchura mínima entre todos los posibles descomposición en árbol de G . En esta definición, el tamaño del conjunto más grande se reduce en uno para que el ancho de árbol de un árbol sea igual a uno.

De manera equivalente, el ancho de árbol de G es uno menor que el tamaño de la camarilla más grande en el gráfico cordal que contiene G con el número de camarilla más pequeño . Se puede obtener un gráfico cordal con este tamaño de camarilla agregando a G un borde entre cada dos vértices que pertenezcan al menos a uno de los conjuntos X _i .

Treewidth también puede caracterizarse en términos de paraísos , funciones que describen una estrategia de evasión para un determinado juego de persecución-evasión definido en un gráfico. Un gráfico G tiene un ancho de árbol k si y solo si tiene un refugio de orden k + 1 pero no de orden superior, donde un refugio de orden k + 1 es una función β que mapea cada conjunto X de a lo sumo k vértices en G en uno de los componentes conectados de G \ X y que obedece a la propiedad de monotonicidad que β ( Y) ⊆ ß ( X ) cuando X ⊆ Y .

Una zarza de orden cuatro en un gráfico de cuadrícula de 3 × 3, cuya existencia muestra que el gráfico tiene un ancho de árbol de al menos 3

También se puede hacer una caracterización similar usando zarzas , familias de subgrafías conectadas que se tocan entre sí (lo que significa que comparten un vértice o están conectadas por un borde). ^[3] El orden de una zarza es el conjunto de golpes más pequeño para la familia de subgrafos, y el ancho de árbol de un gráfico es uno menos que el orden máximo de una zarza.

Ejemplos [ editar ]

Cada gráfico completo K _n tiene un ancho de árbol n  - 1. Esto se ve más fácilmente usando la definición de ancho de árbol en términos de gráficos cordales: el gráfico completo ya es cordal, y agregar más bordes no puede reducir el tamaño de su camarilla más grande.

Un gráfico conectado con al menos dos vértices tiene un ancho de árbol 1 si y solo si es un árbol. Un árbol tiene un ancho de árbol uno por el mismo razonamiento que para los gráficos completos (es decir, es cordal y tiene un tamaño máximo de camarilla dos). Por el contrario, si un gráfico tiene un ciclo, cada terminación cordal del gráfico incluye al menos un triángulo que consta de tres vértices consecutivos del ciclo, de lo que se deduce que su ancho de árbol es al menos dos.

Ancho de árbol acotado [ editar ]

Graficar familias con ancho de árbol acotado [ editar ]

Para cualquier constante fijo k , los gráficos de las treewidth en la mayoría de k son llamados los parciales k -Los árboles . Otras familias de gráficos con ancho de árbol limitado incluyen los gráficos de cactus , pseudoforestas , gráficos de serie en paralelo , gráficos de plano exterior , gráficos de Halin y redes apolíneas . ^[4] Los gráficos de flujo de control que surgen en la compilación de programas estructurados también tienen un ancho de árbol acotado, lo que permite ciertas tareas como la asignación de registrospara ser realizado eficientemente en ellos. ^[5]

Los gráficos planos no tienen un ancho de árbol acotado, porque el gráfico de cuadrícula n × n es un gráfico plano con un ancho de árbol exactamente n . Por lo tanto, si F es una familia de gráficos cerrados menores con un ancho de árbol acotado, no puede incluir todos los gráficos planos. Por el contrario, si algún gráfico plano no puede ocurrir como menor para los gráficos en la familia F , entonces hay una constante k tal que todos los gráficos en F tienen un ancho de árbol como máximo k . Es decir, las siguientes tres condiciones son equivalentes entre sí: ^[6]

1. F es una familia menor cerrada de gráficos de ancho de árbol acotado;
2. Uno de los menores prohibidos que caracterizan F es plano;
3. F es una familia de grafos cerrados menores que no incluye todos los grafos planos.

Menores prohibidos [ editar ]

Los cuatro menores prohibidos para el ancho del árbol 3: K ₅ (arriba a la izquierda), el gráfico del octaedro (abajo a la izquierda), el gráfico de Wagner (arriba a la derecha) y el gráfico del prisma pentagonal (abajo a la derecha)

Para cada valor finito de k , las gráficas de ancho de árbol como máximo k pueden caracterizarse por un conjunto finito de menores prohibidos . (Es decir, cualquier gráfico de ancho de árbol> k incluye uno de los gráficos en el conjunto como un menor). Cada uno de estos conjuntos de menores prohibidos incluye al menos un gráfico plano.

• Para k = 1, el menor prohibido único es un gráfico de ciclo de 3 vértices . ^[7]
• Para k = 2, el menor prohibido único es el gráfico completo de 4 vértices K ₄ . ^[7]
• Para k = 3, hay cuatro menores prohibidos: K ₅ , el gráfico del octaedro , el gráfico de prisma pentagonal y el gráfico de Wagner . De estos, los dos gráficos poliédricos son planos. ^[8]

Para valores mayores de k , el número de menores prohibidos crece al menos tan rápido como el exponencial de la raíz cuadrada de  k . ^[9] Sin embargo, los límites superiores conocidos en el tamaño y el número de menores prohibidos son mucho más altos que este límite inferior. ^[10]

Algoritmos [ editar ]

Calcular el ancho del árbol [ editar ]

Está completo NP para determinar si un gráfico G dado tiene un ancho de árbol como máximo una variable k dada . ^[11] Sin embargo, cuando k es una constante fija, se pueden reconocer los gráficos con el ancho de árbol k , y se puede construir una descomposición del árbol de ancho k para ellos, en tiempo lineal. ^[12] La dependencia del tiempo de este algoritmo con k es exponencial.

Debido a los roles que juega el ancho del árbol en una enorme cantidad de campos, se desarrollaron diferentes algoritmos prácticos y teóricos que computan el ancho del árbol de un gráfico. Dependiendo de la aplicación disponible, uno puede preferir una mejor relación de aproximación, o una mejor dependencia en el tiempo de ejecución del tamaño de la entrada o del ancho del árbol. La siguiente tabla proporciona una descripción general de algunos de los algoritmos de ancho de árbol. aquí$${\ displaystyle k} es el ancho del árbol y $${\ displaystyle n} es el número de vértices de un gráfico de entrada $${\ displaystyle G}. Cada uno de los algoritmos sale a tiempo$${\ displaystyle f (k) \ cdot g (n)}una descomposición de ancho dada en la columna Aproximación. Por ejemplo, el algoritmo de Bodlaender (1996) en el tiempo$${\ displaystyle O (k ^ {O (k ^ {3})}) \ cdot n} construye una descomposición en árbol del gráfico de entrada $${\ displaystyle G} de ancho como máximo $${\ displaystyle k} o informa que el ancho de árbol de $${\ displaystyle G} Es mas que $${\ displaystyle k}. Del mismo modo, el algoritmo de Bodlaender et al. (2016) a tiempo$${\ displaystyle 2 ^ {O (k)} \ cdot n} construye una descomposición en árbol del gráfico de entrada $${\ displaystyle G} de ancho como máximo $${\ displaystyle 5k + 4} o informa que el ancho de árbol de $${\ displaystyle G} Es mas que $${\ displaystyle k}.

Aproximación	f (k)	g (n)	referencia
exacto	$${\ displaystyle O (1)}	$${\ displaystyle O (n ^ {k + 2})}	Arnborg, Corneil y Proskurowski (1987)
$${\ displaystyle 4k + 3}	$${\ displaystyle O (3 ^ {3k})}	$${\ displaystyle O (n ^ {2})}	Robertson y Seymour (1995)
exacto	$${\ displaystyle k ^ {O (k ^ {3})}}	$${\ displaystyle O (n)}	Bodlaender (1996)
$${\ displaystyle O (k \ cdot {\ sqrt {\ log k}})}	$${\ displaystyle O (1)}	$${\ displaystyle n ^ {O (1)}}	Feige, Hajiaghayi y Lee (2008)
$${\ displaystyle 5k + 4}	$${\ displaystyle 2 ^ {O (k)}}	$${\ displaystyle O (n)}	Bodlaender y col. (2016)
$${\ displaystyle k ^ {2}}	$${\ displaystyle O (k ^ {7})}	$${\ displaystyle O (n \ log n)}	Fomin y col. (2018)

Problema no resuelto en matemáticas : ¿Se puede calcular el ancho de árbol de los gráficos planos en tiempo polinómico? (Más problemas no resueltos en matemáticas)

No se sabe si determinar el ancho de árbol de los gráficos planos es NP-completo, o si su ancho de árbol se puede calcular en tiempo polinómico. ^[13]

En la práctica, un algoritmo de Shoikhet & Geiger (1997) puede determinar el ancho de árbol de los gráficos con hasta 100 vértices y el ancho de árbol de hasta 11, encontrando una terminación cordal de estos gráficos con el ancho de árbol óptimo.

Resolviendo otros problemas en gráficos de pequeño ancho de árbol [ editar ]

A principios de la década de 1970, se observó que una gran clase de problemas de optimización combinatoria definidos en los gráficos podría resolverse eficientemente mediante programación dinámica no serial siempre que el gráfico tuviera una dimensión acotada , ^[14] un parámetro que se muestra equivalente a ancho de árbol por Bodlaender (1998) . Más tarde, varios autores observaron de forma independiente a fines de la década de 1980 ^[15] que muchos problemas algorítmicos que son NP completos para gráficos arbitrarios pueden resolverse eficientemente mediante programación dinámica para gráficos de ancho de árbol acotado, utilizando las descomposiciones de árbol de estos gráficos.

Como ejemplo, el problema de colorear un gráfico de ancho de árbol k puede resolverse usando un algoritmo de programación dinámico en una descomposición de árbol del gráfico. Para cada conjunto X _i de la descomposición del árbol, y cada partición de los vértices de X _i en clases de color, el algoritmo determina si ese color es válido y puede extenderse a todos los nodos descendientes en la descomposición del árbol, combinando información de un similar tipo calculado y almacenado en esos nodos. El algoritmo resultante encuentra una coloración óptima de un gráfico n- vértice en el tiempo O ( k ^{k  +  O(1)} n ), un límite de tiempo que hace que este problema sea manejable con parámetros fijos .

Teorema de Courcelle [ editar ]

Artículo principal: teorema de Courcelle

Para una gran clase de problemas, existe un algoritmo de tiempo lineal para resolver un problema de la clase si se proporciona una descomposición de árbol con un ancho de árbol acotado constante. Específicamente, el teorema de Courcelle ^[16] [17] establece que si un problema gráfico puede expresarse en la lógica de gráficos usando lógica monádica de segundo orden , entonces puede resolverse en tiempo lineal en gráficos con ancho de árbol acotado. La lógica monádica de segundo orden es un lenguaje para describir propiedades gráficas que utiliza las siguientes construcciones: operaciones lógicas ($${\ displaystyle \ wedge, \ vee, \ neg, \ Rightarrow}), pruebas de membresía (por ejemplo, $${\ displaystyle e \ en E, v \ en V}), cuantificaciones sobre vértices, aristas, conjuntos de vértices, conjuntos de aristas (p. ej., $${\ displaystyle \ forall} $${\ displaystyle v \ en V}, $${\ displaystyle \ exist} $${\ displaystyle e \ en E}, $${\ displaystyle \ exist} $${\ displaystyle I \ subseteq V}, $${\ displaystyle \ forall} $${\ displaystyle F \ subseteq E}), pruebas de adyacencia ( u es un punto final de e ) y algunas extensiones que permiten cosas como la optimización.

Considere, por ejemplo, el problema de 3 colores para los gráficos. Para un gráfico$${\ displaystyle G = (V, E)}, este problema pregunta si es posible asignar cada vértice $${\ displaystyle v \ en V}uno de los 3 colores de modo que no se asignen dos vértices adyacentes del mismo color. Este problema se puede expresar en lógica monádica de segundo orden de la siguiente manera:

$${\ displaystyle \ exist W_ {1} \ subseteq V: \ exist W_ {2} \ subseteq V: \ exist W_ {3} \ subseteq V: \ forall v \ in V: (v \ in W_ {1} \ vee v \ en W_ {2} \ vee v \ en W_ {3}) \ wedge}

$${\ displaystyle \ forall v \ in V: \ forall w \ in V: (v, w) \ in E \ Rightarrow (\ neg (v \ in W_ {1} \ wedge w \ in W_ {1}) \ wedge \ neg (v \ en W_ {2} \ wedge w \ en W_ {2}) \ wedge \ neg (v \ en W_ {3} \ wedge w \ en W_ {3}))},

dónde $${\ displaystyle W_ {1}, W_ {2}, W_ {3}}representan los subconjuntos de vértices que tienen cada uno de los 3 colores. Por lo tanto, según los resultados de Courcelle, el problema de 3 colores puede resolverse en tiempo lineal para un gráfico dada una descomposición de árbol de ancho de árbol constante acotado.

Parámetros relacionados [ editar ]

Ancho de ruta [ editar ]

El ancho de ruta de un gráfico tiene una definición muy similar al ancho de árbol a través de las descomposiciones de árbol, pero está restringido a las descomposiciones de árbol en las que el árbol subyacente de la descomposición es un gráfico de ruta . Alternativamente, el ancho de ruta puede definirse a partir de gráficos de intervalo de forma análoga a la definición de ancho de árbol a partir de gráficos cordales. Como consecuencia, el ancho de ruta de un gráfico siempre es al menos tan grande como su ancho de árbol, pero solo puede ser mayor por un factor logarítmico. ^[4] Otro parámetro, el ancho de banda del gráfico , tiene una definición análoga de los gráficos de intervalo adecuados , y es al menos tan grande como el ancho de ruta. Otros parámetros relacionados incluyen la profundidad del árbol, un número que está delimitado para una familia de gráfico cerrado menor si y solo si la familia excluye una ruta, y la degeneración , una medida de la dispersión de un gráfico que es como máximo igual a su ancho de árbol.

Tamaño menor de la cuadrícula [ editar ]

Debido a que el treewidth de un n  ×  n gráfico de la red es n , el treewidth de un gráfico G es siempre mayor que o igual al tamaño de la más grande de cuadrícula menor de G . En la otra dirección, el teorema de la cuadrícula menor de Robertson y Seymour muestra que existe una función f tal que el ancho del árbol es como máximo f ( r ) donde r es el tamaño de la cuadrícula menor más grande. ^[18] Los mejores límites conocidos en f son que fdebe ser al menos Ω ( r ^d ) para alguna constante fija d > 0, y como máximo O ( √ r / log r ). ^[19] Se conocen límites más estrictos para las familias de gráficos restringidos, lo que lleva a algoritmos eficientes para muchos problemas de optimización de gráficos en esas familias a través de la teoría de la bidimensionalidad . ^[20] El teorema de la cuadrícula de Halin proporciona un análogo de la relación entre el ancho del árbol y el tamaño menor de la cuadrícula para gráficos infinitos. ^[21]

Diámetro y ancho de árbol local [ editar ]

Se dice que una familia F de gráficos cerrados debajo de los subgrafos tiene un ancho de arbol local limitado , o la propiedad de diametro-arbol de ancho , si el ancho de arbol de los grafos de la familia esta limitado por una funcion de su diametro . Si también se supone que la clase está cerrada al tomar menores , entonces F ha delimitado el ancho de árbol local si y solo si uno de los menores prohibidos para F es un gráfico de vértice . ^[22] Las pruebas originales de este resultado mostraron que el ancho del árbol en una familia de gráficos libres de ápice-menor crece como máximo doblemente exponencialmente en función del diámetro;^[23] más tarde esto se redujo a exponencialmente simple ^[20] y finalmente a un límite lineal. ^{[24] El} ancho de árbol local limitado está estrechamente relacionado con la teoría algorítmica de bidimensionalidad , ^[25] y cada propiedad de gráfico definible en la lógica de primer orden se puede decidir para una familia de gráficos libres de ápice menor en un período de tiempo que es solo un poco superlineal . ^[26]

También es posible que una clase de gráficos que no está cerrada por menores tengan un límite de árbol local limitado. En particular, esto es trivialmente cierto para una clase de gráficos de grados acotados, ya que los subgrafos de diámetro acotado tienen un tamaño acotado. Otro ejemplo está dado por gráficos de 1 plano , gráficos que se pueden dibujar en el plano con un cruce por borde, y más generalmente para los gráficos que se pueden dibujar en una superficie de género acotado con un número acotado de cruces por borde. Al igual que con las familias de gráficos cerrados menores de ancho de árbol local acotado, esta propiedad ha señalado el camino hacia algoritmos de aproximación eficientes para estos gráficos. ^[27]

Número de Hadwiger y funciones S [ editar ]

Halin (1976) define una clase de parámetros gráficos que llama funciones S , que incluyen el ancho del árbol. Estas funciones, desde gráficos hasta enteros, deben ser cero en gráficos sin aristas , ser monótono menor (una función f se denomina "monótono menor" si, cuando H es menor de G , uno tiene f (H ) ≤ f (G)), para aumentar en uno cuando se agrega un nuevo vértice adyacente a todos los vértices anteriores, y tomar el valor más grande de las dos subgrafías a cada lado de un separador de camarillas . El conjunto de todas esas funciones forma una red completabajo las operaciones de minimización y maximización por elementos. El elemento superior en esta red es el ancho del árbol, y el elemento inferior es el número de Hadwiger , el tamaño del menor completo más grande en el gráfico dado.