Un gráfico ordenado es un gráfico con un orden total sobre sus nodos.
En un gráfico ordenado, los padres de un nodo son los nodos adyacentes a él y que lo preceden en el ordenamiento. [1] Más precisamente, es un padre de en el gráfico ordenado si y . El ancho de un nodo es el número de sus padres, y el ancho de un gráfico ordenado es el ancho máximo de sus nodos.
El gráfico inducido de un gráfico ordenado se obtiene añadiendo algunas aristas a un gráfico ordenador, utilizando el método que se describe a continuación. El ancho inducido de un gráfico ordenado es el ancho de su gráfico inducido. [2]
Dado un grafo ordenado, su grafo inducido es otro grafo ordenado obtenido uniendo algunos pares de nodos que son ambos padres de otro nodo. En particular, los nodos se consideran a su vez según el orden, del último al primero. Para cada nodo, si dos de sus padres no están unidos por una arista, se agrega esa arista. En otras palabras, al considerar el nodo , si ambos y son padres de él y no están unidos por una arista, la arista se agrega al grafo. Dado que los padres de un nodo siempre están conectados entre sí, el grafo inducido es siempre cordal .
A modo de ejemplo, se calcula el grafo inducido de un grafo ordenado. El ordenamiento se representa mediante la posición de sus nodos en las figuras: a es el último nodo y d es el primero.
El nodo se considera primero. Sus padres son y , ya que ambos están unidos a y ambos preceden en el orden. Como no están unidos por una arista, se agrega uno.
El nodo se considera segundo. Si bien este nodo solo tiene como padre en el gráfico original, también tiene como padre en el gráfico inducido parcialmente construido. De hecho, se une a y también precede en el ordenamiento. Como resultado, se agrega una arista que une a y .
Considerar no produce ningún cambio, ya que este nodo no tiene padres.
El orden en que se procesan los nodos es importante, ya que las aristas introducidas pueden crear nuevos padres, que luego son relevantes para la introducción de nuevas aristas. El siguiente ejemplo muestra que un orden diferente produce un gráfico inducido diferente del mismo gráfico original. El orden es el mismo que el anterior, pero y están intercambiados.
Como en el caso anterior, tanto y son padres de . Por lo tanto, se añade una arista entre ellos. De acuerdo con el nuevo orden, el segundo nodo que se considera es . Este nodo tiene solo un padre ( ). Por lo tanto, no se añade ninguna arista nueva. El tercer nodo considerado es . Su único padre es . De hecho, y no se unen esta vez. Como resultado, no se introduce ninguna arista nueva. Como tampoco tiene padre, el grafo inducido final es el anterior. Este grafo inducido difiere del producido por el ordenamiento anterior.
