En matemáticas , y, en particular, en teoría de grafos , un grafo enraizado es un grafo en el que se ha distinguido un vértice como raíz. [1] [2] Se han estudiado versiones dirigidas y no dirigidas de gráficos enraizados, y también existen definiciones variantes que permiten múltiples raíces.
Los grafos arraigados también pueden conocerse (según su aplicación) como gráficos puntiagudos o gráficos de flujo . En algunas de las aplicaciones de estos gráficos, existe un requisito adicional de que se pueda acceder al gráfico completo desde el vértice raíz.
En teoría de grafos topológicos , la noción de grafo con raíces puede ampliarse para considerar múltiples vértices o múltiples aristas como raíces. Los primeros a veces se denominan gráficos con raíces de vértices para distinguirlos de los gráficos con raíces de aristas en este contexto. [3] Los gráficos con múltiples nodos designados como raíces también son de cierto interés en combinatoria , en el área de los gráficos aleatorios . [4] Estos gráficos también se denominan gráficos de raíces múltiples . [5]
Los términos gráfico dirigido con raíz o dígrafo con raíz también ven variaciones en las definiciones. El trasplante obvio es considerar un dígrafo enraizado identificando un nodo particular como raíz. [6] [7] Sin embargo, en informática , estos términos comúnmente se refieren a una noción más limitada; es decir, un gráfico dirigido con raíz es un dígrafo con un nodo distinguido r , tal que hay una ruta dirigida desde r a cualquier nodo que no sea r . [8] [9] [10] [11] Los autores que dan la definición más general pueden referirse a gráficos que cumplen con la definición más estrecha como dígrafos con raíces conectadas [6] o gráficos con raíces accesibles (ver § Teoría de conjuntos).
El arte de la programación informática define los dígrafos enraizados de forma un poco más amplia, es decir, un grafo dirigido se llama enraizado si tiene al menos un nodo que puede llegar a todos los demás nodos. Knuth señala que la noción así definida es una especie de intermedia entre las nociones de dígrafo fuertemente conectado y. [12]
En informática , los gráficos arraigados en los que el vértice raíz puede alcanzar todos los demás vértices se denominan gráficos de flujo o diagramas de flujo . [13] A veces se agrega una restricción adicional que especifica que un diagrama de flujo debe tener un único vértice de salida ( sumidero ). [14]
Los gráficos de flujo pueden verse como abstracciones de diagramas de flujo , con los elementos no estructurales (contenidos y tipos de nodos) eliminados. [15] [16] Quizás la subclase más conocida de gráficos de flujo son los gráficos de flujo de control , utilizados en compiladores y análisis de programas . Un gráfico de flujo arbitrario se puede convertir en un gráfico de flujo de control realizando una contracción de borde en cada borde que sea el único borde saliente desde su origen y el único borde entrante hacia su destino. [17] Otro tipo de gráfico de flujo comúnmente utilizado es el gráfico de llamadas , en el que los nodos corresponden a subrutinas completas . [18]
La noción general de gráfico de flujo se ha denominado gráfico de programa , [19] pero el mismo término también se ha utilizado para denotar únicamente gráficos de flujo de control. [20] Los diagramas de flujo también se han denominado diagramas de flujo sin etiquetar [21] y diagramas de flujo adecuados . [15] Estos gráficos se utilizan a veces en pruebas de software . [15] [18]
Cuando se requiere que tengan una única salida, los gráficos de flujo tienen dos propiedades que no comparten con los gráficos dirigidos en general: los gráficos de flujo se pueden anidar, lo que es el equivalente a una llamada de subrutina (aunque no existe la noción de pasar parámetros), y los gráficos de flujo pueden también ser secuenciado, lo que equivale a la ejecución secuencial de dos fragmentos de código. [22] Los gráficos de flujo primarios se definen como gráficos de flujo que no se pueden descomponer mediante anidamiento o secuenciación utilizando un patrón elegido de subgrafos, por ejemplo, las primitivas de la programación estructurada . [23] Se han realizado investigaciones teóricas para determinar, por ejemplo, la proporción de gráficos de flujo primario dado un conjunto elegido de gráficos. [24]
Peter Aczel ha utilizado gráficos dirigidos enraizados de modo que cada nodo sea accesible desde la raíz (a los que él llama gráficos puntiagudos accesibles ) para formular el axioma antifundamento de Aczel en la teoría de conjuntos no bien fundamentados . En este contexto, cada vértice de un gráfico puntiagudo accesible modela un conjunto (no bien fundamentado) dentro de la teoría de conjuntos (no bien fundamentada) de Aczel, y un arco desde un vértice v hasta un vértice w modela que v es un elemento. de w . El axioma anti-fundamento de Aczel establece que cada gráfico puntiagudo accesible modela una familia de conjuntos (no bien fundamentados) de esta manera. [25]
Cualquier juego combinatorio puede asociarse a un grafo dirigido con raíz cuyos vértices son posiciones del juego, cuyas aristas son movimientos y cuya raíz es la posición inicial del juego. Este gráfico es importante en el estudio de la complejidad del juego , donde la complejidad del espacio de estados es el número de vértices del gráfico.
El número de gráficos no dirigidos enraizados para 1, 2, ... nodos es 1, 2, 6, 20, 90, 544, ... (secuencia A000666 en OEIS ).
Un caso especial de interés son los árboles enraizados , los árboles con un vértice radicular distinguido. Si los caminos dirigidos desde la raíz en el dígrafo enraizado se restringen adicionalmente a ser únicos, entonces la noción obtenida es la de arborescencia (enraizada) , el equivalente en grafo dirigido de un árbol enraizado. [7] Un gráfico enraizado contiene una arborescencia con la misma raíz si y sólo si se puede alcanzar el gráfico completo desde la raíz, y los científicos informáticos han estudiado problemas algorítmicos para encontrar arborescencias óptimas. [26]
Los gráficos enraizados se pueden combinar utilizando el producto de gráficos enraizados . [27]
En este contexto, un dígrafo arraigado Δ = ( V , E , r ) se llama conectado (o 1-conexo ) si hay un camino dirigido desde la raíz a cada vértice.Véase en particular la pág. 307.
Un subdígrafo enraizado
F
es una
arborescencia enraizada
si el vértice raíz ∗ está en
F
y, para cada vértice
v
en
F
, hay un camino dirigido único en
F
desde ∗ a
v
. Así, las arborescencias enraizadas en dígrafos corresponden a árboles enraizados en grafos no dirigidos.
Un gráfico dirigido con raíz o un gráfico de flujo G = ( V , A , r ) es un gráfico dirigido con un vértice r distinguido tal que hay un camino dirigido en G desde r hasta cada vértice v en V − r .. Véase en particular la pág. 122.
un dígrafo
con raíz
es un triple
G
= (
V
,
E
,
r
) donde (
V
∪ {
r
},
E
) es un dígrafo y
r
es un vértice específico llamado raíz, de modo que existe un camino desde
r
a cada vértice de
V.
. Véase en particular la pág. 524.
Un dígrafo enraizado es un dígrafo conectado con un único nodo raíz que es el antepasado de todos los demás nodos del dígrafo.
Se dice que está enraizado si existe al menos una raíz, es decir, al menos un vértice R tal que exista un camino orientado de V a R para todo V ≠ R .