Grafo ordenado

Un grafo ordenado es un grafo que tiene un orden total sobre sus nodos.

En un grafo ordenado, los padres de un nodo son los nodos que son adyacentes a él y lo preceden en el orden. ^{[ 1 ]} Más precisamente,${\displaystyle n}$es padre de${\displaystyle m}$en el grafo ordenado${\displaystyle \langle N,E,<\rangle }$si${\displaystyle (n,m)\in E}$y${\displaystyle n<m}$El ancho de un nodo es el número de sus padres, y el ancho de un grafo ordenado es el ancho máximo de sus nodos.

El grafo inducido de un grafo ordenado se obtiene añadiendo algunas aristas a un grafo de ordenación, utilizando el método descrito a continuación. El ancho inducido de un grafo ordenado es el ancho de su grafo inducido. ^{[ 2 ]}

Dado un grafo ordenado, su grafo inducido es otro grafo ordenado obtenido al unir algunos pares de nodos que son ambos padres de otro nodo. En particular, los nodos se consideran por turnos 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${\displaystyle n}$, si ambos${\displaystyle m}$y${\displaystyle l}$son padres de él y no están unidos por una arista, la arista${\displaystyle (m,l)}$se agrega al grafo. Dado que los padres de un nodo siempre están conectados entre sí, el grafo inducido siempre es cordal .

Como ejemplo, se calcula el grafo inducido de un grafo ordenado. El orden se representa mediante la posición de sus nodos en las figuras: a es el último nodo y d es el primero.

Nodo${\displaystyle a}$se considera primero. Sus padres son${\displaystyle b}$y${\displaystyle c}$, ya que ambos están unidos a${\displaystyle a}$y ambos preceden${\displaystyle a}$en el ordenamiento. Como no están unidos por una arista, se agrega una.

Nodo${\displaystyle b}$se considera segundo. Mientras que este nodo solo tiene${\displaystyle d}$como padre en el gráfico original, también tiene${\displaystyle c}$como padre en el grafo inducido parcialmente construido. De hecho,${\displaystyle c}$está unido a${\displaystyle b}$y también preceder${\displaystyle b}$en el ordenamiento. Como resultado, una unión de bordes${\displaystyle c}$y${\displaystyle d}$se añade.

En vista de${\displaystyle d}$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 grafo inducido diferente del mismo grafo original. El grafo es el mismo que el anterior, pero${\displaystyle b}$y${\displaystyle c}$se intercambian en el orden.

Al igual que en el caso anterior, ambos${\displaystyle b}$y${\displaystyle c}$son padres de${\displaystyle a}$Por lo tanto, se agrega una arista entre ellos. Según el nuevo orden, el segundo nodo que se considera es${\displaystyle c}$. Este nodo tiene un solo padre (${\displaystyle b}$). Por lo tanto, no se agrega ninguna arista nueva. El tercer nodo considerado es${\displaystyle b}$Su único progenitor es${\displaystyle d}$. Ahora,${\displaystyle b}$y${\displaystyle c}$se unen como antes pero debido al orden diferente,${\displaystyle c}$no es padre de${\displaystyle b}$Como resultado, no se introduce ninguna arista nueva entre${\displaystyle c}$y${\displaystyle d}$esta vez. Desde${\displaystyle d}$No tiene padre, el gráfico inducido final es el de arriba. Este gráfico inducido difiere del producido por el ordenamiento anterior.

• Grafo dirigido
• Consistencia local

• Dechter, Rina (2003). Procesamiento de restricciones . Morgan Kaufmann.ISBN 1-55860-890-7