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 lo preceden en el orden. [1] Más precisamente, es 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 agregando algunos bordes a un gráfico ordenado, 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 gráfico ordenado, su gráfico inducido es otro gráfico ordenado obtenido al unir algunos pares de nodos que son 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 un borde, ese borde se agrega. En otras palabras, al considerar el nodo, si ambos y son padres de ella y no están unidos por un borde, el borde se agrega al gráfico. Dado que los padres de un nodo siempre están conectados entre sí, el gráfico inducido siempre es cordal .
Como ejemplo, se calcula el gráfico inducido de un gráfico ordenado. El orden está representado por la posición de sus nodos en las figuras: a es el último nodo y d es el primero.
El gráfico original. | Edge agregó considerando a los padres de | Edge agregó considerando a los padres de |
Nodo se considera primero. Sus padres son y , ya que ambos están unidos a y ambos preceden en el pedido. Como no están unidos por un borde, se agrega uno.
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. En efecto, está unido a y también preceden en el pedido. Como resultado, un borde que une y está agregado.
Considerando no produce ningún cambio, ya que este nodo no tiene padres.
El procesamiento de los nodos en orden es importante, ya que los bordes introducidos pueden crear nuevos padres, que luego son relevantes para la introducción de nuevos bordes. 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 se intercambian.
Mismo gráfico, pero el orden de y se intercambia | Gráfico después de considerar |
Como en el caso anterior, ambos y son padres de . Por lo tanto, se agrega un borde entre ellos. Según el nuevo orden, el segundo nodo que se considera es. Este nodo tiene solo un padre (). Por lo tanto, no se agrega ninguna nueva ventaja. El tercer nodo considerado es. Su único padre es. En efecto, y no se unen esta vez. Como resultado, no se introduce una nueva ventaja. Desdetampoco tiene padre, el gráfico inducido final es el de arriba. Este gráfico inducido difiere del producido por el pedido anterior.
Ver también
Referencias
- Dechter, Rina (2003). Procesamiento de restricciones . Morgan Kaufmann.ISBN 1-55860-890-7