Gráfico trapezoidal
En la teoría de grafos , los gráficos trapezoidales son gráficos de intersección de trapezoides entre dos líneas horizontales. Son una clase de gráficos de co-comparabilidad que contienen gráficos de intervalo y gráficos de permutación como subclases. Un gráfico es un gráfico trapezoidal si existe un conjunto de trapezoides correspondientes a los vértices del gráfico de modo que dos vértices estén unidos por un borde si y solo si los trapezoides correspondientes se cruzan. Los gráficos trapezoidales fueron introducidos por Dagan , Golumbic y Pinter en 1988. Existen algoritmos para el número cromático, ponderadoconjunto independiente , cobertura de camarilla y camarilla de peso máximo.
Dado un canal, un par de dos líneas horizontales, un trapezoide entre estas líneas está definido por dos puntos en la parte superior y dos puntos en la línea inferior. Un gráfico es un gráfico trapezoidal si existe un conjunto de trapezoides correspondientes a los vértices del gráfico de modo que dos vértices estén unidos por un borde si y solo si los trapezoides correspondientes se cruzan. La dimensión de orden de intervalo de un conjunto parcialmente ordenado ,, es el número mínimo d de órdenes de intervalo P 1 … P d tal que P = P 1 ∩… ∩P d . La gráfica de incomparabilidad de un conjunto parcialmente ordenado es la gráfica no dirigida donde x es adyacente ay en G si y solo si x yy son incomparables en P. Un gráfico no dirigido es un gráfico trapezoidal si y solo si es el gráfico de incomparabilidad de un orden parcial que tiene una dimensión de orden de intervalo como máximo 2. [1]
Los problemas de encontrar grupos máximos y de colorear gráficos trapezoidales están relacionados con problemas de enrutamiento de canales en el diseño de VLSI . Dados algunos terminales etiquetados en el lado superior e inferior de un canal de dos lados, los terminales con la misma etiqueta se conectarán en una red común. Esta red puede estar representada por un trapezoide que contiene los terminales más a la derecha y los terminales más a la izquierda con la misma etiqueta. Las redes pueden enrutarse sin intersección si y solo si los trapezoides correspondientes no se cruzan. Por lo tanto, el número de capas necesarias para enrutar las redes sin intersección es igual al número cromático del gráfico.
Los trapezoides se pueden usar para representar un gráfico trapezoidal usando la definición de gráfico trapezoidal. La representación trapezoidal de un gráfico trapezoidal se puede ver en la Figura 1.
Rectángulos dominantes, o representación de caja, mapea los puntos en la parte inferior de las dos líneas de la representación trapezoide como ubicados en el eje x y los de la línea superior en el eje y del plano euclidiano. Cada trapezoide corresponde entonces a una caja de eje paralelo en el plano. Usando la noción de un orden de dominancia (en R K , se dice que x está dominado por y , denotado x < y , si x i es menor que y i para i = 1,…, k ), decimos que una caja b domina una casilla b ' si la esquina inferior deb domina la esquina superior de b ' . Además, si una de las dos casillas domina a la otra, decimos que son comparables. De lo contrario, son incomparables. Por lo tanto, dos trapezoides están separados exactamente si sus cajas correspondientes son comparables. La representación de caja es útil porque el orden de dominancia asociado permite que se utilicen algoritmos de línea de barrido. [2]
Los gráficos de bitolerancia son gráficos de incomparabilidad de un orden de bitolerancia. Una orden es una orden de bitolerancia si y solo si hay intervalos I x y números reales t 1 ( x ) y t r ( x ) asignados a cada vértice x de tal manera que x < y si y solo si la superposición de I x e I y es menor que t r ( x ) y t 1 ( y ) y el centro de I x es menor que el centro de I y . [3] En 1993, Langley demostró que los gráficos de bitolerancia acotada son equivalentes a la clase de gráficos trapezoidales. [4]
