En matemáticas , y en particular en teoría de grafos , un grafo con raíz 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 grafos con raíz, y también existen definiciones variantes que permiten múltiples raíces.
Los grafos con raíz también pueden conocerse (según su aplicación) como grafos puntiagudos o grafos de flujo . En algunas de las aplicaciones de estos grafos, existe un requisito adicional de que todo el grafo sea accesible desde el vértice raíz.
En la teoría de grafos topológicos , la noción de grafo con raíz puede extenderse para considerar múltiples vértices o múltiples aristas como raíces. Los primeros a veces se denominan grafos con raíz en vértices para distinguirlos de los grafos con raíz en aristas en este contexto. [3] Los grafos con múltiples nodos designados como raíces también son de cierto interés en combinatoria , en el área de grafos aleatorios . [4] Estos grafos también se denominan grafos con múltiples raíces . [5]
Los términos grafo dirigido con raíz o dígrafo con raíz también ven variación en las definiciones. El trasplante obvio es considerar un dígrafo con raíz 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 estrecha; a saber, un grafo dirigido con raíz es un dígrafo con un nodo distinguido r , de modo que hay un camino dirigido desde r a cualquier nodo distinto de r . [8] [9] [10] [11] Los autores que dan la definición más general pueden referirse a los grafos que cumplen con la definición más estrecha como dígrafos con raíz conexos [6] o grafos con raíz accesibles (véase § Teoría de conjuntos).
En The Art of Computer Programming, los dígrafos con raíz se definen de forma un poco más amplia, es decir, un grafo dirigido se denomina con raíz si tiene al menos un nodo que puede alcanzar a todos los demás nodos. Knuth señala que la noción así definida es una especie de intermedio entre las nociones de dígrafo fuertemente conectado y dígrafo conectado . [12]
En informática , los grafos con raíz en los que el vértice raíz puede alcanzar todos los demás vértices se denominan grafos de flujo o flowgraphs . [13] A veces se añade una restricción adicional que especifica que un grafo 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 puede convertirse en un gráfico de flujo de control realizando una contracción de borde en cada borde que sea el único borde saliente de su fuente y el único borde entrante en 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]
El concepto 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 gráficos de flujo también se han denominado gráficos de flujo sin etiqueta [21] y gráficos de flujo propios [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 también se pueden secuenciar, lo que es el equivalente a la ejecución secuencial de dos piezas de código. [22] Los gráficos de flujo principales se definen como gráficos de flujo que no se pueden descomponer mediante anidación o secuenciación utilizando un patrón elegido de subgráficos, por ejemplo, los primitivos de la programación estructurada . [23] Se han realizado investigaciones teóricas para determinar, por ejemplo, la proporción de gráficos de flujo principales dado un conjunto elegido de gráficos. [24]
Peter Aczel ha utilizado grafos dirigidos con raíz de manera que cada nodo sea alcanzable desde la raíz (a los que llama grafos apuntados accesibles ) para formular el axioma antifundamental de Aczel en la teoría de conjuntos no bien fundados . En este contexto, cada vértice de un grafo apuntado accesible modela un conjunto (no bien fundado) dentro de la teoría de conjuntos (no bien fundados) 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 antifundamental de Aczel establece que cada grafo apuntado accesible modela una familia de conjuntos (no bien fundados) de esta manera. [25]
Cualquier juego combinatorio puede asociarse a un grafo dirigido con raíz cuyos vértices son posiciones del juego, cuyos bordes son movimientos y cuya raíz es la posición inicial del juego. Este grafo 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 grafo.
El número de gráficos no dirigidos con raíz para 1, 2, ... nodos es 1, 2, 6, 20, 90, 544, ... (secuencia A000666 en la OEIS ).
Un caso especial de interés son los árboles con raíz , los árboles con un vértice raíz distinguido. Si los caminos dirigidos desde la raíz en el dígrafo con raíz se restringen adicionalmente para que sean únicos, entonces la noción obtenida es la de arborescencia (con raíz) —el equivalente en grafo dirigido de un árbol con raíz. [7] Un grafo con raíz contiene una arborescencia con la misma raíz si y solo si se puede llegar a todo el grafo desde la raíz, y los científicos informáticos han estudiado problemas algorítmicos para encontrar arborescencias óptimas. [26]
Los gráficos con raíz se pueden combinar utilizando el producto raíz de gráficos . [27]
En este contexto, un dígrafo con raíz Δ = ( V , E , r ) se llama conexo (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 ∗ hasta
v
. Por lo tanto, las arborescencias enraizadas en dígrafos corresponden a árboles enraizados en grafos no dirigidos.
Un
grafo dirigido con raízo
un
grafo de flujo
G
= (
V
,
A
,
r
) es un grafo dirigido con un vértice distinguido
r
tal que hay un camino dirigido en
G
desde
r
a cada vértice
v
en
V
−
r
.
. Véase en particular la pág. 122.
Un dígrafo
enraizado
es un triple
G
=(
V
,
E
,
r
) donde (
V
∪ {
r
},
E
) es un dígrafo y
r
es un vértice especificado llamado raíz tal que existe un camino desde
r
a cada vértice de
V
.
. Véase en particular la pág. 524.
Un
dígrafo con raízes
un dígrafo conectado con un solo nodo raíz que es el ancestro de todos los demás nodos del dígrafo.
que tiene raíz si existe al menos una raíz, es decir, al menos un vértice R tal que existe un camino orientado de V a R para todo V ≠ R .