Grafo acíclico dirigido

Un DAG

Su reducción transitiva

La relación de alcanzabilidad de un DAG se puede formalizar como un orden parcial ≤ en los vértices del DAG. En este orden parcial, dos vértices u y v se ordenan como u ≤ v exactamente cuando existe un camino dirigido de u a v en el DAG; es decir, cuando u puede alcanzar a v (o v es alcanzable desde u ). ^{[ 4 ]} Sin embargo, diferentes DAG pueden dar lugar a la misma relación de alcanzabilidad y al mismo orden parcial. ^{[ 5 ]} Por ejemplo, un DAG con dos aristas u → v y v → w tiene la misma relación de alcanzabilidad que el DAG con tres aristas u → v , v → w y u → w . Ambos DAG producen el mismo orden parcial, en el que los vértices se ordenan como u ≤ v ≤ w .

El cierre transitivo de un DAG es el grafo con el mayor número de aristas que tiene la misma relación de alcanzabilidad que el DAG. Tiene una arista u → v para cada par de vértices ( u , v ) en la relación de alcanzabilidad ≤ del DAG, y por lo tanto puede considerarse como una traducción directa de la relación de alcanzabilidad ≤ a términos de teoría de grafos. El mismo método de traducir órdenes parciales a DAG funciona de forma más general: para cada conjunto parcialmente ordenado finito ( S , ≤) , el grafo que tiene un vértice para cada elemento de S y una arista para cada par de elementos en ≤ es automáticamente un DAG transitivamente cerrado, y tiene ( S , ≤) como su relación de alcanzabilidad. De esta manera, cada conjunto parcialmente ordenado finito puede representarse como un DAG.

La reducción transitiva de un DAG es el grafo con la menor cantidad de aristas que tiene la misma relación de alcanzabilidad que el DAG. Tiene una arista u → v para cada par de vértices ( u , v ) en la relación de cobertura de la relación de alcanzabilidad ≤ del DAG. Es un subgrafo del DAG, formado al descartar las aristas u → v para las cuales el DAG también contiene un camino dirigido más largo de u a v . Al igual que el cierre transitivo, la reducción transitiva está definida de forma única para los DAG. En cambio, para un grafo dirigido que no es acíclico, puede haber más de un subgrafo mínimo con la misma relación de alcanzabilidad. ^{[ 6 ]} Las reducciones transitivas son útiles para visualizar los órdenes parciales que representan, porque tienen menos aristas que otros grafos que representan los mismos órdenes y, por lo tanto, conducen a dibujos de grafos más simples . Un diagrama de Hasse de un orden parcial es un dibujo de la reducción transitiva en el que la orientación de cada arista se muestra colocando el vértice inicial de la arista en una posición más baja que su vértice final. ^{[ 7 ]}

Ordenación topológica de un grafo dirigido acíclico: cada arista va desde una posición anterior en la ordenación (superior izquierda) hasta una posición posterior (inferior derecha). Un grafo dirigido es acíclico si y solo si posee una ordenación topológica.

Al agregar las aristas rojas al grafo acíclico dirigido azul se produce otro DAG, el cierre transitivo del grafo azul. Para cada arista roja o azul u → v , v es alcanzable desde u : existe un camino azul que comienza en u y termina en v .

Un ordenamiento topológico de un grafo dirigido es un ordenamiento de sus vértices en una secuencia, de tal manera que para cada arista, el vértice inicial aparece antes en la secuencia que el vértice final. Un grafo con un ordenamiento topológico no puede tener ciclos, ya que la arista que apunta al primer vértice de un ciclo tendría que estar orientada incorrectamente. Por lo tanto, todo grafo con un ordenamiento topológico es acíclico. A la inversa, todo grafo dirigido acíclico tiene al menos un ordenamiento topológico. La existencia de un ordenamiento topológico puede utilizarse, por consiguiente, como una definición equivalente de un grafo dirigido acíclico: son precisamente los grafos que poseen ordenamientos topológicos. ^{[ 2 ]} En general, este ordenamiento no es único; un DAG tiene un ordenamiento topológico único si y solo si tiene un camino dirigido que contiene todos los vértices, en cuyo caso el ordenamiento coincide con el orden en que aparecen los vértices en el camino. ^{[ 8 ]}

La familia de ordenaciones topológicas de un DAG es la misma que la familia de extensiones lineales de la relación de alcanzabilidad para el DAG, ^{[ 9 ]} por lo que cualesquiera dos grafos que representen el mismo orden parcial tienen el mismo conjunto de órdenes topológicas.

El problema de enumeración de grafos , que consiste en contar grafos dirigidos acíclicos, fue estudiado por Robinson (1973) . ^{[ 10 ]} El número de DAG en n vértices etiquetados, para n  =  0, 1, 2, 3, … (sin restricciones en el orden en que aparecen estos números en un ordenamiento topológico del DAG) es

1, 1, 3, 25, 543, 29281, 3781503, … (secuencia A003024 en el OEIS ) .

Estos números pueden calcularse mediante la relación de recurrencia.

${\displaystyle a_{n}=\sum _{k=1}^{n}(-1)^{k-1}{n \choose k}2^{k(nk)}a_{nk}.}$^{[ 10 ]}

Eric W. Weisstein conjeturó, ^{[ 11 ]} y McKay et al. (2004) demostraron, que los mismos números cuentan las matrices (0,1) para las cuales todos los autovalores son números reales positivos . La demostración es biyectiva : una matriz A es una matriz de adyacencia de un DAG si y solo si A  + I  es una matriz (0,1) con todos los autovalores positivos, donde I denota la matriz identidad . Dado que un DAG no puede tener bucles , su matriz de adyacencia debe tener una diagonal cero, por lo que agregar I preserva la propiedad de que todos los coeficientes de la matriz sean 0 o 1. ^{[ 12 ]}

Un multiárbol , un DAG en el que el subgrafo alcanzable desde cualquier vértice induce un árbol no dirigido (por ejemplo, en rojo).

Un poliárbol , un DAG formado al orientar las aristas de un árbol no dirigido.

Un multiárbol (también llamado grafo fuertemente no ambiguo o manglar ) es un DAG en el que existe como máximo un camino dirigido entre dos vértices cualesquiera. De forma equivalente, es un DAG en el que el subgrafo alcanzable desde cualquier vértice induce un árbol no dirigido . ^{[ 13 ]}

Un poliárbol (también llamado árbol dirigido ) es un multiárbol formado al orientar las aristas de un árbol no dirigido. ^{[ 14 ]}

Una arborescencia es un poliárbol formado al orientar las aristas de un árbol no dirigido alejándolas de un vértice particular, llamado raíz de la arborescencia.

La ordenación topológica es el problema algorítmico de encontrar una ordenación topológica de un DAG dado. Se puede resolver en tiempo lineal . ^{[ 15 ]} El algoritmo de Kahn para la ordenación topológica construye directamente la ordenación de vértices. Mantiene una lista de vértices que no tienen aristas entrantes de otros vértices que no se hayan incluido ya en la ordenación topológica parcialmente construida; inicialmente, esta lista consta de los vértices sin ninguna arista entrante. Luego, agrega repetidamente un vértice de esta lista al final de la ordenación topológica parcialmente construida y comprueba si sus vecinos deben agregarse a la lista. El algoritmo termina cuando todos los vértices se han procesado de esta manera. ^{[ 16 ]} Alternativamente, se puede construir una ordenación topológica invirtiendo una numeración de postorden de un recorrido de grafo en profundidad . ^{[ 15 ]}

También es posible comprobar si un grafo dirigido dado es un DAG en tiempo lineal, ya sea intentando encontrar un orden topológico y luego probando para cada arista si el orden resultante es válido ^{[ 17 ]} o, alternativamente, para algunos algoritmos de ordenación topológica, verificando que el algoritmo ordena correctamente todos los vértices sin incurrir en una condición de error. ^{[ 16 ]}

Cualquier grafo no dirigido puede convertirse en un DAG eligiendo un orden total para sus vértices y dirigiendo cada arista desde el extremo anterior del orden hasta el extremo posterior. La orientación resultante de las aristas se denomina orientación acíclica . Diferentes órdenes totales pueden dar lugar a la misma orientación acíclica, por lo que un grafo de n vértices puede tener menos de n ! orientaciones acíclicas. El número de orientaciones acíclicas es igual a | χ (−1) | , donde χ es el polinomio cromático del grafo dado. ^{[ 18 ]}

Cualquier grafo dirigido puede convertirse en un DAG eliminando un conjunto de vértices de retroalimentación o un conjunto de arcos de retroalimentación , un conjunto de vértices o aristas (respectivamente) que toca todos los ciclos. Sin embargo, el conjunto más pequeño de este tipo es NP-difícil de encontrar. ^{[ 19 ]} Un grafo dirigido arbitrario también puede transformarse en un DAG, llamado su condensación , contrayendo cada uno de sus componentes fuertemente conectados en un único supervértice. ^{[ 20 ]} Cuando el grafo ya es acíclico, sus conjuntos de vértices de retroalimentación y conjuntos de arcos de retroalimentación más pequeños están vacíos , y su condensación es el propio grafo.

El cierre transitivo de un DAG dado, con n vértices y m aristas, puede construirse en tiempo O ( mn ) utilizando una búsqueda en anchura o una búsqueda en profundidad para comprobar la alcanzabilidad desde cada vértice. ^{[ 21 ]} Alternativamente, puede resolverse en tiempo O ( nω ), ^donde ω <  2,373  es el exponente de los algoritmos de multiplicación de matrices ; esto supone una mejora teórica respecto al límite O ( mn ) para grafos densos . ^{[ 22 ]}

En todos estos algoritmos de cierre transitivo, es posible distinguir pares de vértices que son alcanzables por al menos un camino de longitud dos o más de pares que solo pueden conectarse por un camino de longitud uno. La reducción transitiva consiste en las aristas que forman caminos de longitud uno que son los únicos caminos que conectan sus extremos. Por lo tanto, la reducción transitiva puede construirse en los mismos límites de tiempo asintótico que el cierre transitivo. ^{[ 23 ]}

El problema de cierre toma como entrada un grafo dirigido acíclico ponderado por vértices y busca el peso mínimo (o máximo) de un cierre: un conjunto de vértices C , tal que ninguna arista salga de C. El problema puede formularse para grafos dirigidos sin la suposición de aciclicidad, pero sin mayor generalidad, ya que en este caso es equivalente al mismo problema en la condensación del grafo. Puede resolverse en tiempo polinomial mediante una reducción al problema de flujo máximo . ^{[ 24 ]}

Algunos algoritmos se simplifican al aplicarse a grafos acíclicos dirigidos (DAG) en lugar de grafos generales, basándose en el principio de ordenación topológica. Por ejemplo, es posible encontrar los caminos más cortos y más largos desde un vértice inicial dado en DAG en tiempo lineal procesando los vértices en orden topológico y calculando la longitud del camino para cada vértice como la longitud mínima o máxima obtenida a través de cualquiera de sus aristas entrantes. ^{[ 25 ]} En cambio, para grafos arbitrarios, el camino más corto puede requerir algoritmos más lentos, como el algoritmo de Dijkstra o el algoritmo de Bellman-Ford , ^{[ 26 ]} y encontrar los caminos más largos en grafos arbitrarios es un problema NP-difícil . ^{[ 27 ]}

Las representaciones gráficas acíclicas dirigidas de ordenaciones parciales tienen muchas aplicaciones en la planificación de sistemas de tareas con restricciones de ordenación. ^{[ 28 ]} Una clase importante de problemas de este tipo se refiere a colecciones de objetos que necesitan actualizarse, como las celdas de una hoja de cálculo después de que se haya modificado una de ellas, o los archivos objeto de un programa informático después de que se haya modificado su código fuente . En este contexto, un grafo de dependencia es un grafo que tiene un vértice por cada objeto que se va a actualizar y una arista que conecta dos objetos cuando uno de ellos necesita actualizarse antes que el otro. Un ciclo en este grafo se denomina dependencia circular y, por lo general, no está permitido, ya que no habría forma de planificar de manera consistente las tareas involucradas en el ciclo. Los grafos de dependencia sin dependencias circulares forman DAG. ^{[ 29 ]}

Por ejemplo, cuando cambia una celda de una hoja de cálculo , es necesario recalcular los valores de otras celdas que dependen directa o indirectamente de la celda modificada. Para este problema, las tareas a programar son los recálculos de los valores de las celdas individuales de la hoja de cálculo. Las dependencias surgen cuando una expresión en una celda utiliza un valor de otra celda. En tal caso, el valor utilizado debe recalcularse antes que la expresión que lo utiliza. Ordenar topológicamente el grafo de dependencias y utilizar este orden topológico para programar las actualizaciones de las celdas permite actualizar toda la hoja de cálculo con una sola evaluación por celda. ^{[ 30 ]} Problemas similares de ordenación de tareas surgen en los makefiles para la compilación de programas ^{[ 30 ]} y en la programación de instrucciones para la optimización de programas informáticos de bajo nivel. ^{[ 31 ]}

La técnica de evaluación y revisión de programas (PERT), un método para la gestión de grandes proyectos humanos y una de las primeras aplicaciones de los DAG, utiliza una formulación de restricciones de programación basada en DAG algo diferente. En este método, los vértices de un DAG representan hitos de un proyecto en lugar de tareas específicas a realizar. En cambio, una tarea o actividad se representa mediante una arista del DAG, que conecta dos hitos que marcan el inicio y la finalización de la tarea. Cada arista se etiqueta con una estimación del tiempo que le llevará a un equipo de trabajadores realizar la tarea. La ruta más larga en este DAG representa la ruta crítica del proyecto, la que controla el tiempo total del mismo. Los hitos individuales se pueden programar según la longitud de las rutas más largas que terminan en sus vértices. ^{[ 32 ]}

Un grafo dirigido acíclico puede utilizarse para representar una red de elementos de procesamiento. En esta representación, los datos entran a un elemento de procesamiento a través de sus aristas de entrada y salen de él a través de sus aristas de salida.

Por ejemplo, en el diseño de circuitos electrónicos, los bloques lógicos combinacionales estáticos pueden representarse como un sistema acíclico de compuertas lógicas que calcula una función de una entrada, donde la entrada y la salida de la función se representan como bits individuales . En general, la salida de estos bloques no puede usarse como entrada a menos que sea capturada por un registro o elemento de estado que mantenga sus propiedades acíclicas. ^{[ 33 ]} Los esquemas de circuitos electrónicos, ya sea en papel o en una base de datos, son una forma de grafos acíclicos dirigidos que utilizan instancias o componentes para formar una referencia dirigida a un componente de nivel inferior. Los circuitos electrónicos en sí mismos no son necesariamente acíclicos ni dirigidos.

Los lenguajes de programación de flujo de datos describen sistemas de operaciones sobre flujos de datos y las conexiones entre las salidas de algunas operaciones y las entradas de otras. Estos lenguajes pueden ser útiles para describir tareas repetitivas de procesamiento de datos, en las que se aplica la misma colección de operaciones conectadas acíclicamente a muchos elementos de datos. Se pueden ejecutar como un algoritmo paralelo en el que cada operación es realizada por un proceso paralelo tan pronto como se dispone de un nuevo conjunto de entradas. ^{[ 34 ]}

En los compiladores , el código lineal (es decir, secuencias de instrucciones sin bucles ni bifurcaciones condicionales) puede representarse mediante un DAG que describe las entradas y salidas de cada una de las operaciones aritméticas realizadas dentro del código. Esta representación permite al compilador realizar la eliminación de subexpresiones comunes de manera eficiente. ^{[ 35 ]} En un nivel superior de organización del código, el principio de dependencias acíclicas establece que las dependencias entre módulos o componentes de un sistema de software grande deben formar un grafo dirigido acíclico. ^{[ 36 ]}

Las redes neuronales de alimentación directa son otro ejemplo.

Los grafos en los que los vértices representan eventos que ocurren en un momento definido, y donde las aristas siempre apuntan de un vértice anterior a uno posterior, son necesariamente dirigidos y acíclicos. La ausencia de ciclos se debe a que el tiempo asociado a un vértice siempre aumenta al seguir cualquier camino dirigido en el grafo, por lo que nunca se puede regresar a un vértice en un camino. Esto refleja nuestra intuición natural de que la causalidad implica que los eventos solo pueden afectar al futuro, nunca al pasado, y por lo tanto no existen bucles causales . Un ejemplo de este tipo de grafo dirigido acíclico son los que se encuentran en el enfoque de conjuntos causales de la gravedad cuántica, aunque en este caso los grafos considerados son transitivamente completos . En el ejemplo de historial de versiones que se muestra a continuación, cada versión del software está asociada a un tiempo único, normalmente el momento en que se guardó, confirmó o publicó la versión. En los ejemplos de grafos de citas que se muestran a continuación, los documentos se publican en un momento dado y solo pueden hacer referencia a documentos anteriores.

A veces, los eventos no están asociados con un tiempo físico específico. Siempre que pares de eventos tengan una relación puramente causal, es decir, que las aristas representen relaciones causales entre los eventos, tendremos un grafo acíclico dirigido. ^{[ 37 ]} Por ejemplo, una red bayesiana representa un sistema de eventos probabilísticos como vértices en un grafo acíclico dirigido, en el que la probabilidad de un evento puede calcularse a partir de las probabilidades de sus predecesores en el DAG. ^{[ 38 ]} En este contexto, el grafo moral de un DAG es el grafo no dirigido creado al agregar una arista (no dirigida) entre todos los padres del mismo vértice (a veces llamado matrimonio ), y luego reemplazar todas las aristas dirigidas por aristas no dirigidas. ^{[ 39 ]} Otro tipo de grafo con una estructura causal similar es un diagrama de influencia , cuyos vértices representan decisiones que deben tomarse o información desconocida, y cuyas aristas representan influencias causales de un vértice a otro. ^{[ 40 ]} En epidemiología , por ejemplo, estos diagramas se utilizan a menudo para estimar el valor esperado de diferentes opciones de intervención. ^{[ 41 ] [ 42 ]}

Lo contrario también es cierto. Es decir, en cualquier aplicación representada por un grafo acíclico dirigido, existe una estructura causal, ya sea un orden explícito o temporal, como en el ejemplo, o un orden que puede derivarse de la estructura del grafo. Esto se debe a que todos los grafos acíclicos dirigidos poseen un orden topológico ; es decir, existe al menos una forma de ordenar los vértices de manera que todas las aristas apunten en la misma dirección a lo largo de dicho orden.

Los árboles genealógicos pueden considerarse grafos dirigidos acíclicos, con un vértice para cada miembro de la familia y una arista para cada relación padre-hijo. ^{[ 43 ]} A pesar del nombre, estos grafos no son necesariamente árboles debido a la posibilidad de matrimonios entre parientes (de modo que un hijo tenga un ancestro común tanto por parte materna como paterna), lo que provoca el colapso del pedigrí . ^{[ 44 ]} Los grafos de descendencia matrilineal (relaciones madre-hija) y descendencia patrilineal (relaciones padre-hijo) son árboles dentro de este grafo. Dado que nadie puede convertirse en su propio ancestro, los árboles genealógicos son acíclicos. ^{[ 45 ]}

El historial de versiones de un sistema de control de revisiones distribuido , como Git , generalmente tiene la estructura de un grafo dirigido acíclico, en el que hay un vértice para cada revisión y una arista que conecta pares de revisiones que se derivaron directamente entre sí. Estos no son árboles en general debido a las fusiones. ^{[ 46 ]}

En muchos algoritmos aleatorios de geometría computacional , el algoritmo mantiene un DAG de historial que representa el historial de versiones de una estructura geométrica a lo largo de una secuencia de cambios en la estructura. Por ejemplo, en un algoritmo incremental aleatorio para la triangulación de Delaunay , la triangulación cambia reemplazando un triángulo por tres triángulos más pequeños cuando se agrega cada punto, y mediante operaciones de "inversión" que reemplazan pares de triángulos por un par de triángulos diferente. El DAG de historial para este algoritmo tiene un vértice para cada triángulo construido como parte del algoritmo, y aristas desde cada triángulo hacia los otros dos o tres triángulos que lo reemplazan. Esta estructura permite responder de manera eficiente a las consultas de ubicación de puntos : para encontrar la ubicación de un punto de consulta q en la triangulación de Delaunay, se sigue una ruta en el DAG de historial, moviéndose en cada paso al triángulo de reemplazo que contiene q . El triángulo final alcanzado en esta ruta debe ser el triángulo de Delaunay que contiene q . ^{[ 47 ]}

En un grafo de citas, los vértices son documentos con una única fecha de publicación. Las aristas representan las citas de la bibliografía de un documento a otros documentos necesariamente anteriores. El ejemplo clásico proviene de las citas entre artículos académicos, como se señala en el artículo de 1965 "Redes de artículos científicos" ^{[ 48 ]} de Derek J. de Solla Price, quien posteriormente produjo el primer modelo de una red de citas, el modelo Price . ^{[ 49 ]} En este caso, el número de citas de un artículo es simplemente el grado de entrada del vértice correspondiente de la red de citas. Esta es una medida importante en el análisis de citas . Las sentencias judiciales proporcionan otro ejemplo, ya que los jueces respaldan sus conclusiones en un caso recordando otras decisiones anteriores tomadas en casos anteriores. Un último ejemplo lo proporcionan las patentes, que deben hacer referencia al estado de la técnica anterior , patentes anteriores que son relevantes para la reivindicación de patente actual. Al tener en cuenta las propiedades especiales de los grafos acíclicos dirigidos, se pueden analizar redes de citas con técnicas no disponibles cuando se analizan los grafos generales considerados en muchos estudios que utilizan el análisis de redes . Por ejemplo, la reducción transitiva ofrece nuevas perspectivas sobre las distribuciones de citas encontradas en diferentes aplicaciones, destacando claras diferencias en los mecanismos que crean redes de citas en diferentes contextos. ^{[ 50 ]} Otra técnica es el análisis de ruta principal , que rastrea los enlaces de citas y sugiere las cadenas de citas más significativas en un grafo de citas dado .

El modelo de Price es demasiado simple para ser un modelo realista de una red de citas, pero es lo suficientemente simple como para permitir soluciones analíticas para algunas de sus propiedades. Muchas de estas se pueden encontrar utilizando resultados derivados de la versión no dirigida del modelo de Price , el modelo de Barabási-Albert . Sin embargo, dado que el modelo de Price proporciona un grafo acíclico dirigido, es un modelo útil cuando se buscan cálculos analíticos de propiedades únicas de los grafos acíclicos dirigidos. Por ejemplo, la longitud del camino más largo, desde el n-ésimo nodo agregado a la red hasta el primer nodo de la red, escala como ^{[ 51 ].}${\displaystyle \ln(n)}$.

Los grafos acíclicos dirigidos también pueden usarse como una representación compacta de una colección de secuencias. En este tipo de aplicación, se encuentra un DAG en el que los caminos forman las secuencias dadas. Cuando muchas de las secuencias comparten las mismas subsecuencias, estas subsecuencias compartidas pueden representarse mediante una parte compartida del DAG, lo que permite que la representación use menos espacio que si se enumeraran todas las secuencias por separado. Por ejemplo, el grafo de palabras acíclico dirigido es una estructura de datos en ciencias de la computación formada por un grafo acíclico dirigido con una sola fuente y con aristas etiquetadas con letras o símbolos; los caminos desde la fuente hasta los sumideros en este grafo representan un conjunto de cadenas , como palabras en inglés. ^{[ 52 ]} Cualquier conjunto de secuencias puede representarse como caminos en un árbol, formando un vértice de árbol para cada prefijo de una secuencia y haciendo que el padre de uno de estos vértices represente la secuencia con un elemento menos; el árbol formado de esta manera para un conjunto de cadenas se llama trie .

De manera similar, un árbol de búsqueda binaria puede considerarse como un DAG con raíz donde los caminos representan ordenaciones de claves, aunque carece de la compresión de fusión de caminos que se encuentra en los DAG más complejos. ^{[ 53 ]} Un grafo de palabras acíclico dirigido ahorra espacio en comparación con un trie al permitir que los caminos diverjan y se vuelvan a unir, de modo que un conjunto de palabras con los mismos sufijos posibles puede representarse mediante un único vértice del árbol. ^{[ 54 ]}

La misma idea de usar un DAG para representar una familia de caminos aparece en el diagrama de decisión binario , ^{[ 55 ] [ 56 ]} una estructura de datos basada en DAG para representar funciones binarias. En un diagrama de decisión binario, cada vértice que no es un sumidero está etiquetado con el nombre de una variable binaria, y cada sumidero y cada arista están etiquetados con un 0 o un 1. El valor de la función para cualquier asignación de verdad a las variables es el valor en el sumidero encontrado al seguir un camino, comenzando desde el único vértice fuente, que en cada vértice que no es un sumidero sigue la arista saliente etiquetada con el valor de la variable de ese vértice. Así como los grafos de palabras acíclicos dirigidos pueden verse como una forma comprimida de tries , los diagramas de decisión binarios pueden verse como formas comprimidas de árboles de decisión que ahorran espacio al permitir que los caminos se vuelvan a unir cuando coinciden en los resultados de todas las decisiones restantes. ^{[ 57 ]}