En teoría de grafos , los grafos trapezoidales son grafos de intersección de trapecios entre dos líneas horizontales. Son una clase de grafos de co-comparabilidad que contienen grafos de intervalo y grafos de permutación como subclases. Un grafo es un grafo trapezoidal si existe un conjunto de trapecios correspondientes a los vértices del grafo de manera que dos vértices están unidos por una arista si y solo si los trapecios correspondientes se intersecan. Los grafos trapezoidales fueron introducidos por Dagan, Golumbic y Pinter en 1988. Existen algoritmos para número cromático, conjunto independiente ponderado , cobertura de camarilla y camarilla ponderada máxima.
Dado un canal, un par de dos líneas horizontales, un trapezoide entre estas líneas se define por dos puntos en la línea superior y dos puntos en la línea inferior. Un grafo es un grafo trapezoidal si existe un conjunto de trapecios correspondientes a los vértices del grafo tales que dos vértices están unidos por una arista si y solo si los trapecios correspondientes se intersecan. 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 tales que P = P 1 ∩…∩P d . El grafo de incomparabilidad de un conjunto parcialmente ordenado es el grafo no dirigido donde x es adyacente a y en G si y solo si x e y son incomparables en P. Un grafo no dirigido es un grafo trapezoidal si y solo si es el grafo de incomparabilidad de un orden parcial que tiene una dimensión de orden de intervalo de como máximo 2. [1]
Los problemas de encontrar camarillas máximas y de colorear gráficos trapezoidales están relacionados con los problemas de enrutamiento de canales en el diseño 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 se puede representar mediante un trapezoide que contiene los terminales más a la derecha y los más a la izquierda con la misma etiqueta. Las redes se pueden enrutar sin intersección si y solo si los trapecios correspondientes no se intersecan. Por lo tanto, la cantidad de capas necesarias para enrutar las redes sin intersección es igual al número cromático del gráfico.
Los trapecios se pueden utilizar para representar un gráfico trapezoidal utilizando la definición de gráfico trapezoidal. La representación trapezoidal de un gráfico trapezoidal se puede ver en la Figura 1.
Los rectángulos dominantes, o representación en forma de caja, asignan los puntos de la línea inferior de las dos líneas de la representación trapezoidal como si estuvieran en el eje x y los de la línea superior como si estuvieran en el eje y del plano euclidiano. Cada trapezoide corresponde entonces a una caja paralela al eje en el plano. Utilizando la noción de un orden de dominancia (en R K , se dice que x está dominada por y , denotado x < y , si x i es menor que y i para i = 1, …, k ), decimos que una caja b domina a una caja b' si la esquina inferior de b domina la esquina superior de b' . Además, si una de las dos cajas domina a la otra decimos que son comparables. De lo contrario, son incomparables. Por lo tanto, dos trapecios son disjuntos exactamente si sus cajas correspondientes son comparables. La representación en forma de caja es útil porque el orden de dominancia asociado permite utilizar algoritmos de línea de barrido. [2]
Los grafos de bitolerancia son grafos de incomparabilidad de un orden de bitolerancia. Un orden es un 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 tanto t r ( x ) como t 1 ( y ) y el centro de I x es menor que el centro de I y . [3] En 1993, Langley demostró que los grafos de bitolerancia acotados son equivalentes a la clase de grafos trapezoidales. [4]
La clase de grafos trapezoidales contiene propiamente la unión de grafos de intervalo y de permutación y es equivalente a los grafos de incomparabilidad de conjuntos parcialmente ordenados que tienen una dimensión de orden de intervalo de como máximo dos. Los grafos de permutación pueden considerarse como el caso especial de los grafos trapezoidales cuando cada trapezoide tiene área cero. Esto ocurre cuando ambos puntos del trapezoide en el canal superior están en la misma posición y ambos puntos en el canal inferior están en la misma posición.
Como todos los gráficos de incomparabilidad, los gráficos trapezoidales son perfectos .
Los grafos trapezoidales circulares son una clase de grafos propuesta por Felsner et al. en 1993. Son una superclase de la clase de grafos trapezoidales y también contienen grafos circulares y grafos de arco circular. Un trapezoide circular es la región en un círculo que se encuentra entre dos cuerdas que no se cruzan y un grafo trapezoidal circular es el grafo de intersección de familias de trapecios circulares en un círculo común. Existe un algoritmo para el problema de conjuntos independientes de ponderación máxima y un algoritmo para el problema de camarilla de ponderación máxima.
Los grafos k -trapezoidales son una extensión de los grafos trapezoidales a órdenes de dimensión superiores. Fueron propuestos por primera vez por Felsner y se basan en la definición de cajas dominantes que se trasladan a dimensiones superiores en las que un punto x está representado por un vector . Al utilizar árboles de rango de ( k − 1) dimensiones para almacenar y consultar coordenadas, los algoritmos de Felsner para número cromático, camarilla máxima y conjunto independiente máximo se pueden aplicar a los grafos k -trapezoidales en el tiempo.
Los algoritmos para grafos trapezoidales deben compararse con los algoritmos para grafos de co-comparabilidad general. Para esta clase más grande de grafos, el conjunto independiente máximo y el problema de cobertura de camarilla mínima pueden resolverse en el tiempo. [5] Dagan et al. propusieron por primera vez un algoritmo para colorear grafos trapezoidales, donde n es el número de nodos y k es el número cromático del grafo. Más tarde, utilizando la representación de caja de grafos trapezoidales, Felsner publicó algoritmos para número cromático, conjunto independiente ponderado, cobertura de camarilla y camarilla ponderada máxima. Todos estos algoritmos requieren espacio. Estos algoritmos se basan en el dominio asociado en la representación de caja que permite utilizar algoritmos de línea de barrido. Felsner propone utilizar árboles balanceados que pueden realizar operaciones de inserción, eliminación y consulta en el tiempo, lo que da como resultado algoritmos.
Para determinar si un grafo es un grafo trapezoidal, busque una orientación transitiva en el complemento de . Dado que los grafos trapezoidales son un subconjunto de los grafos de co-comparabilidad, si es un grafo trapezoidal, su complemento debe ser un grafo de comparabilidad. Si no existe una orientación transitiva del complemento , no es un grafo trapezoidal. Si existe, pruebe para ver si el orden dado por es un orden trapezoidal. El algoritmo más rápido para el reconocimiento del orden trapezoidal fue propuesto por McConnell y Spinrad en 1994, con un tiempo de ejecución de . El proceso reduce la cuestión de dimensión de intervalo 2 a un problema de cubrir un grafo bipartito asociado por grafos de cadena (grafos sin 2K 2 inducido ). [6] Mertzios y Corneil demostraron que, utilizando la división de vértices, el problema de reconocimiento de grafos trapezoidales tenía éxito en el tiempo, donde denota el número de aristas. Este proceso implica aumentar un gráfico dado y luego transformar el gráfico aumentado reemplazando cada uno de los vértices del gráfico original por un par de vértices nuevos. Este "gráfico dividido" es un gráfico de permutación con propiedades especiales si un solo si es un gráfico trapezoidal. [7]
