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 la raíz. [1] [2] Se han estudiado versiones tanto dirigidas como no dirigidas de grafos con raíces, y también hay definiciones variantes que permiten múltiples raíces.
Los gráficos enraizados 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 todo el gráfico sea accesible desde el vértice raíz.
Variaciones
En la teoría de grafos topológicos , la noción de grafo con raíces puede extenderse para considerar múltiples vértices o aristas como raíces. Los primeros a veces se denominan gráficos con raíces en vértices para distinguirlos de los gráficos con raíces en los bordes en este contexto. [3] Los gráficos con múltiples nodos designados como raíces también son de cierto interés en la 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 arraigado o dígrafo arraigado también ven variaciones en las definiciones. El trasplante obvio es considerar un dígrafo enraizado identificando un nodo en particular como raíz. [6] [7] Sin embargo, en ciencias de la computación , 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 existe 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 estos 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 ligeramente más amplia, es decir, un gráfico dirigido se denomina enraizado si tiene al menos un nodo que puede alcanzar 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 conectado . [12]
Aplicaciones
Gráficos de flujo
En ciencias de la computación , gráficos arraigadas en la que el vértice de la raíz pueden llegar a todos los otros vértices se llaman diagramas de flujo o flowgraphs . [13] A veces se agrega una restricción adicional que especifica que un diagrama de flujo también debe tener un único vértice de salida ( sumidero ). [14]
Los diagramas de flujo pueden verse como abstracciones de diagramas de flujo , con los elementos no estructurales (contenido 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 diagrama de flujo arbitrario puede convertirse en un diagrama de flujo de control realizando una contracción de borde en cada borde que es el único borde saliente de su fuente y el único borde entrante en su objetivo. [17] Otro tipo de diagrama 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 gráficos de flujo también se han denominado gráficos de flujo sin etiquetar , [21] y gráficos de flujo adecuados . [15] Estos gráficos se utilizan a veces en pruebas de software . [15] [18]
Cuando se requiere tener una sola salida, los gráficos de flujo tienen dos propiedades que no se comparten con los gráficos dirigidos en general. Los gráficos de flujo se pueden anidar, lo que equivale 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 equivale a la ejecución secuencial de dos piezas de código. [22] Los gráficos de flujo primarios 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, 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]
Teoría de conjuntos
Peter Aczel ha utilizado gráficos dirigidos arraigadas de tal manera que cada nodo es accesible desde la raíz (que él llama gráficos accesibles en punta ) para formular axioma anti-fundación de Aczel en la teoría de conjuntos no bien fundada . En este contexto, cada vértice de un gráfico puntiagudo accesible modela un conjunto (no bien fundado) dentro de la teoría de conjuntos (no bien fundada) 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]
Teoría de juegos combinatorios
Dado un juego puramente combinatorio , hay un gráfico dirigido con raíz asociado cuyos vértices son posiciones de juego y cuyos bordes son movimientos, y el recorrido del gráfico a partir de la raíz se utiliza para crear un árbol de juego . Si el gráfico contiene ciclos dirigidos , entonces una posición en el juego podría repetirse infinitas veces y , por lo general, se necesitan reglas para evitar que el juego continúe indefinidamente. De lo contrario, el gráfico es un gráfico acíclico dirigido y, si no es un árbol enraizado , el juego tiene transposiciones . Este gráfico y su topología es importante en el estudio de la complejidad del juego , donde la complejidad del espacio de estado es el número de vértices en el gráfico, la duración promedio del juego es el número promedio de vértices atravesados desde la raíz hasta un vértice sin sucesores directos. , y el factor de ramificación promedio de un árbol de juego es el grado medio del gráfico.
Enumeración combinatoria
El número de gráficos arraigados no dirigidos para 1, 2, ... nodos es 1, 2, 6, 20, 90, 544, ... (secuencia A000666 en la OEIS )
Conceptos relacionados
Un caso especial de interés son los árboles enraizados , los árboles con un vértice radical distinguido. Si los caminos dirigidos desde la raíz en el dígrafo enraizado están además restringidos para ser únicos, entonces la noción obtenida es la de arborescencia (enraizada) , el equivalente en gráfico dirigido de un árbol enraizado. [7] Un gráfico con raíces contiene una arborescencia con la misma raíz si y solo si se puede llegar a todo el gráfico 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 enraizado de los gráficos . [27]
Ver también
- grafo conectado a k-vértices
- conjunto puntiagudo
Referencias
- ^ Zwillinger, Daniel (2011), Tablas y fórmulas matemáticas estándar de CRC, 32ª edición , CRC Press, p. 150, ISBN 978-1-4398-3550-0
- ^ Harary, Frank (1955), "El número de gráficos lineales, dirigidos, enraizados y conectados", Transactions of the American Mathematical Society , 78 (2): 445–463, doi : 10.1090 / S0002-9947-1955-0068198- 2 , MR 0068198. Ver pág. 454.
- ^ Gross, Jonathan L .; Yellen, Jay; Zhang, Ping (2013), Manual de teoría de grafos (2ª ed.), CRC Press, págs. 764–765, ISBN 978-1-4398-8018-0
- ^ Spencer, Joel (2001), La extraña lógica de los gráficos aleatorios , Springer Science & Business Media, capítulo 4, ISBN 978-3-540-41654-8
- ^ Harary (1955 , p. 455).
- ^ a b Björner, Anders ; Ziegler, Günter M. (1992), "8. Introduction to greedoids" (PDF) , en White, Neil (ed.), Matroid Applications , Encyclopedia of Mathematics and its Applications, 40 , Cambridge: Cambridge University Press, págs. 284 –357 , doi : 10.1017 / CBO9780511662041.009 , ISBN 0-521-38165-7, MR 1165537 , Zbl 0772.05026 ,
En este contexto, un dígrafo con raíz Δ = ( V , E , r ) se llama conectado (o 1-conectado ) si hay un camino dirigido desde la raíz a cada vértice.
Ver en particular la p. 307. - ^ a b Gordon, Gary; McMahon, Elizabeth (febrero de 1989), "Un polinomio greedoide que distingue arborescencias arraigadas" (PDF) , Proceedings of the American Mathematical Society , 107 (2): 287, CiteSeerX 10.1.1.308.2526 , doi : 10.1090 / s0002-9939- 1989-0967486-0 ,
Un subdígrafo con raíz F es una arborescencia con raíz si el vértice raíz ∗ está en F y, para cada vértice v en F , hay una trayectoria dirigida única en F de ∗ a v . Así, las arborescencias enraizadas en dígrafos corresponden a árboles enraizados en gráficos no dirigidos.
- ^ Ramachandran, Vijaya (1988), "Algoritmos paralelos rápidos para gráficos de flujo reducibles", Cálculos concurrentes : 117-138, doi : 10.1007 / 978-1-4684-5511-3_8 , ISBN 978-1-4684-5513-7,
Un grafo dirigido con raíz o un grafo de flujo G = ( V , A , r ) es un grafo dirigido con un vértice distinguido r tal que hay una trayectoria dirigida en G desde r hasta cada vértice v en V - r .
. Ver en particular la p. 122. - ^ Okamoto, Yoshio; Nakamura, Masataka (2003), "La caracterización menor prohibida de antimatroides de búsqueda de líneas de dígrafos arraigados" (PDF) , Discrete Applied Mathematics , 131 (2): 523-533, doi : 10.1016 / S0166-218X (02) 00471- 7 ,
Un dígrafo con raíz es un triple G = ( V , E , r ) donde ( V ∪ { r }, E ) es un dígrafo yr es un vértice específico llamado raíz, de modo que existe una ruta de r a cada vértice de V .
. Ver en particular la p. 524. - ^ Jain, Abhinandan (2010), Dinámica de robots y multicuerpo: análisis y algoritmos , Springer Science & Business Media, p. 136, ISBN 978-1-4419-7267-5,
Un dígrafo con raíz es un dígrafo conectado con un único nodo raíz que es el antepasado de todos los demás nodos del dígrafo.
- ^ Chen, Xujin (2004), "An Efficient Algorithm for Finding Maximum Cycle Packings in Reducible Flow Graphs" (PDF) , Lecture Notes in Computer Science , 3341 : 306–317, CiteSeerX 10.1.1.894.5261 , doi : 10.1007 / 978- 3-540-30551-4_28 , hdl : 10722/48600 , ISBN 978-3-540-24131-7,
Un grafo dirigido arraigada o un gráfico de flujo es un dígrafo G con un vértice distinguido r , llamado su raíz , de manera que hay un camino en G de r a cada vértice en G .
. - ^ Knuth, Donald (1997), "2.3.4.2. Árboles orientados", El arte de la programación informática , 1 (3ª ed.), Pearson Education, p. 372, ISBN 0-201-89683-4,
Se dice estar arraigado si hay al menos una raíz, es decir, al menos un vértice R de tal manera que hay un camino orientado de V a R para todos V ≠ R .
- ^ Gross, Yellen y Zhang (2013 , p. 1372).
- ^ Fenton, Norman Elliott; Hill, Gillian A. (1993), Construcción y análisis de sistemas: un marco lógico y matemático , McGraw-Hill, p. 319, ISBN 978-0-07-707431-9.
- ^ a b c Zuse, Horst (1998), A Framework of Software Measurement , Walter de Gruyter, págs. 32–33, ISBN 978-3-11-080730-1
- ^ Samaroo, Angelina; Thompson, Geoff; Williams, Peter (2010), Software Testing: An ISTQB-ISEB Foundation Guide , BCS, The Chartered Institute, p. 108, ISBN 978-1-906124-76-2
- ^ Tarr, Peri L .; Wolf, Alexander L. (2011), Ingeniería de software: las contribuciones continuas de Leon J. Osterweil , Springer Science & Business Media, p. 58, ISBN 978-3-642-19823-6
- ^ a b Jalote, Pankaj (1997), Un enfoque integrado a la ingeniería de software , Springer Science & Business Media, p. 372 , ISBN 978-0-387-94899-7
- ^ Thulasiraman, K .; Swamy, MNS (1992), Gráficos: teoría y algoritmos , John Wiley & Sons, p. 361, ISBN 978-0-471-51356-8
- ^ Cechich, Alejandra; Piattini, Mario; Vallecillo, Antonio (2003), Calidad del software basado en componentes: métodos y técnicas , Springer Science & Business Media, p. 105, ISBN 978-3-540-40503-0
- ^ Beineke, Lowell W .; Wilson, Robin J. (1997), Conexiones de gráficos: relaciones entre la teoría de gráficos y otras áreas de las matemáticas , Clarendon Press, p. 237 , ISBN 978-0-19-851497-8
- ^ Fenton y Hill (1993 , p. 323).
- ^ Fenton y Hill (1993 , p. 339).
- ^ Cooper, C. (2008), "Enumeración asintótica de diagramas de flujo de unión de predicado", Combinatoria, probabilidad y computación , 5 (3): 215-226, doi : 10.1017 / S0963548300001991
- ^ Aczel, Peter (1988), Conjuntos no bien fundados (PDF) , CSLI Lecture Notes, 14 , Stanford, CA: Universidad de Stanford, Centro para el estudio del lenguaje y la información, ISBN 0-937073-22-9, LCCN 87-17857 , MR 0940014 , archivado desde el original (PDF) el 26 de marzo de 2015
- ^ Drescher, Matthew; Vetta, Adrian (2010), "Un algoritmo de aproximación para el problema de arborescencia máxima de la extensión de las hojas" , ACM Trans. Algoritmos , 6 (3): 46: 1–46: 18, doi : 10.1145 / 1798596.1798599 , S2CID 13987985.
- ^ Godsil, CD ; McKay, BD (1978), "Un nuevo producto gráfico y su espectro" (PDF) , Bull. Austral. Matemáticas. Soc. , 18 (1): 21-28, doi : 10.1017 / S0004972700007760 , MR 0494910
Otras lecturas
- McMahon, Elizabeth W. (1993), "Sobre el polinomio greedoide para gráficos con raíces y dígrafos con raíces", Journal of Graph Theory , 17 (3): 433–442, doi : 10.1002 / jgt.3190170316
- Gordon, Gary (2001), "Un polinomio característico para gráficos con raíces y dígrafos con raíces", Matemáticas discretas , 232 (1–3): 19–33, doi : 10.1016 / S0012-365X (00) 00186-2
enlaces externos
- Weisstein, Eric W. "Gráfico con raíces" . MathWorld .