Hispanopedia Wiki
Articulo de referencia

Grafo enraizado

En matemáticas , y en particular en teoría de grafos , un grafo con raíz es un grafo en el que un vértice ha sido distinguido como la raíz. [ 1 ] [ 2 ] Se han estudiado versione...

Hispanopedia WikiContenido en espanolLectura gratuita

En matemáticas , y en particular en teoría de grafos , un grafo con raíz es un grafo en el que un vértice ha sido distinguido como la 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.

Ejemplos de grafos con raíz y algunas variantes. Un digrafo con la raíz colocada de tal manera que cada vértice tiene exactamente un camino dirigido hacia él desde la raíz es una arborescencia .

Los grafos con raíz también pueden conocerse (según su aplicación) como grafos con puntos o grafos de flujo . En algunas aplicaciones de estos grafos, existe el requisito adicional de que todo el grafo sea alcanzable desde el vértice raíz.

Variaciones

En la teoría topológica de grafos , la noción de grafo con raíz puede extenderse para considerar múltiples vértices o múltiples aristas como raíces. A los primeros se les llama a veces 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 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 enraizado o digrafo enraizado también presentan variaciones en sus definiciones. La adaptación obvia consiste en considerar un digrafo enraizado identificando un nodo particular como raíz. [ 6 ] [ 7 ] Sin embargo, en informática , estos términos suelen referirse a una noción más restringida; a saber, un grafo dirigido enraizado es un digrafo con un nodo distinguido r , tal que existe 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 la definición más restringida como digrafos enraizados conectados [ 6 ] o grafos enraizados accesibles (véase §  Teoría de conjuntos ).

El libro El arte de la programación informática define los grafos dirigidos con raíz de forma algo 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 término intermedio entre las nociones de grafo dirigido fuertemente conexo y conexo . [ 12 ]

Aplicaciones

Diagramas de flujo

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 . [ 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 grafos de flujo pueden considerarse 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 grafos de flujo sean los grafos de flujo de control , utilizados en compiladores y análisis de programas . Un grafo de flujo arbitrario puede convertirse en un grafo de flujo de control realizando una contracción de aristas en cada arista que sea la única arista saliente de su origen y la única arista entrante a su destino. [ 17 ] Otro tipo de grafo de flujo comúnmente utilizado es el grafo de llamadas , en el que los nodos corresponden a subrutinas completas . [ 18 ]

La noción general de grafo de flujo se ha denominado grafo de programa , [ 19 ] pero el mismo término también se ha utilizado para denotar únicamente grafos de flujo de control. [ 20 ] Los grafos de flujo también se han denominado grafos de flujo sin etiquetar [ 21 ] y grafos de flujo propiamente dichos . [ 15 ] Estos grafos se utilizan a veces en las pruebas de software . [ 15 ] [ 18 ]

Cuando se requiere una única salida, los grafos de flujo tienen dos propiedades que no comparten con los grafos dirigidos en general: los grafos de flujo pueden anidarse, lo que equivale a una llamada a subrutina (aunque no existe la noción de pasar parámetros), y los grafos de flujo también pueden secuenciarse, lo que equivale a la ejecución secuencial de dos fragmentos de código. [ 22 ] Los grafos de flujo primos se definen como grafos de flujo que no pueden descomponerse 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 grafos de flujo primos dado un conjunto elegido de grafos. [ 24 ]

teoría de conjuntos

Peter Aczel ha utilizado grafos dirigidos con raíz, de modo que cada nodo es alcanzable desde la raíz (a los que denomina grafos accesibles con punto de mira ), para formular el axioma de antifundación de Aczel en la teoría de conjuntos no bien fundados . En este contexto, cada vértice de un grafo accesible con punto de mira 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 de antifundación de Aczel establece que todo grafo accesible con punto de mira modela una familia de conjuntos (no bien fundados) de esta manera. [ 25 ]

Teoría de juegos combinatorios

Cualquier juego combinatorio puede asociarse con un grafo dirigido con raíz, cuyos vértices representan las posiciones del juego, cuyas aristas representan los movimientos y cuya raíz es la posición inicial. Este grafo es importante para el estudio de la complejidad del juego , donde la complejidad del espacio de estados es el número de vértices del grafo.

enumeración combinatoria

El número de grafos no dirigidos con raíz para 1, 2, ... nodos es 1, 2, 6, 20, 90, 544, ... (secuencia A000666 en el OEIS ) .

Un caso especial de interés son los árboles con raíz , aquellos con un vértice raíz distintivo. Si además se restringe la unicidad de los caminos dirigidos desde la raíz en el digrafo con raíz, se obtiene la noción de arborescencia (con raíz) , el equivalente en grafos dirigidos 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 alcanzar todo el grafo desde la raíz, y los informáticos han estudiado problemas algorítmicos para encontrar arborescencias óptimas. [ 26 ]

Los grafos con raíz se pueden combinar utilizando el producto con raíz de grafos . [ 27 ]

Véase también

Referencias

  1. ↑ Zwillinger, Daniel (2011), Tablas y fórmulas matemáticas estándar de CRC, 32.ª edición , CRC Press, pág.  150, ISBN 978-1-4398-3550-0
  2. ↑ Harary, Frank (1955), "El número de grafos 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 Véase la página  454.
  3. ↑ Gross, Jonathan L.; Yellen, Jay; Zhang, Ping (2013), Handbook of Graph Theory (2.ª ed.), CRC Press, pp. 764–765 , ISBN   978-1-4398-8018-0
  4. ↑ Spencer, Joel (2001), La extraña lógica de los grafos aleatorios , Springer Science & Business Media, capítulo 4, ISBN 978-3-540-41654-8
  5. ↑ Harary (1955 , p. 455) . 
  6. 1 2 Björner, Anders ; Ziegler, Günter M. (1992), "8. Introducción a los greedoides" (PDF) , en White, Neil (ed.), Matroid Applications , Encyclopedia of Mathematics and its Applications, vol. 40, Cambridge: Cambridge University Press, pp. 284–357 , doi : 10.1017/CBO9780511662041.009 , ISBN   0-521-38165-7, MR 1165537 , Zbl 0772.05026 , En este contexto, un digrafo con raíz Δ = ( V , E , r ) se denomina conexo (o 1-conexo ) si existe un camino dirigido desde la raíz a cada vértice.  Véase en particular la página  307.
  7. 1 2 Gordon, Gary; McMahon, Elizabeth (febrero de 1989), "Un polinomio greedoid que distingue arborescencias enraizadas" (PDF) , Actas de la Sociedad Matemática Americana , 107 (2): 287, CiteSeerX 10.1.1.308.2526 , doi : 10.1090/s0002-9939-1989-0967486-0 , Un subdigrafo 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 digrafos corresponden a árboles enraizados en grafos no dirigidos. 
  8. ↑ Ramachandran, Vijaya (1988), "Algoritmos paralelos rápidos para grafos de flujo reducibles", Concurrent Computations : 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 existe un camino dirigido en G desde r a cada vértice v en V − r .{{citation}}: CS1 maint: parámetro de trabajo con ISBN ( enlace ) . Véase en particular la página  122.
  9. ↑ Okamoto, Yoshio; Nakamura, Masataka (2003), "The forbidden minor characterization of line-search antimatroids of rooted digraphs" (PDF) , Discrete Applied Mathematics , 131 (2): 523–533 , doi : 10.1016/S0166-218X(02)00471-7 , Un digrafo enraizado es una tripleta G = ( V , E , r ) donde ( V ∪ { r }, E ) es un digrafo 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ágina  524.
  10. ↑ Jain, Abhinandan (2010), Robot and Multibody Dynamics: Analysis and Algorithms , Springer Science & Business Media, p. 136, ISBN  978-1-4419-7267-5Un digrafo enraizado es un digrafo conectado con un único nodo raíz que es el ancestro de todos los demás nodos del digrafo.
  11. ↑ Chen, Xujin; Zang, Wenan (2006), "Un algoritmo eficiente para encontrar empaquetamientos de ciclos máximos en grafos de flujo reducibles", Algorithmica , 44 (3): 195– 211, doi : 10.1007/s00453-005-1174-x , hdl : 10722/48600 , MR 2199991 , S2CID 5235131  
  12. ↑ Knuth, Donald (1997), "2.3.4.2. Árboles orientados", El arte de la programación informática , vol. 1 (3.ª ed.), Pearson Education, pág. 372, ISBN    0-201-89683-4Se dice que tiene raíz si hay 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.
  13. ↑ Gross, Yellen y Zhang (2013 , pág. 1372) . 
  14. ↑ Fenton, Norman Elliott; Hill, Gillian A. (1993), Construcción y análisis de sistemas: un marco matemático y lógico , McGraw-Hill, pág. 319, ISBN  978-0-07-707431-9.
  15. ^ Zuse , Horst (1998), Un marco de medición de software , Walter de Gruyter, págs. 32-33 , ISBN  978-3-11-080730-1
  16. ↑ 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
  17. ↑ Tarr, Peri L.; Wolf, Alexander L. (2011), Ingeniería de software: Las continuas contribuciones de Leon J. Osterweil , Springer Science & Business Media, pág. 58, ISBN  978-3-642-19823-6
  18. 1 2 Jalote, Pankaj (1997), Un enfoque integrado para la ingeniería de software , Springer Science & Business Media, pág. 372 , ISBN  978-0-387-94899-7
  19. ↑ Thulasiraman, K.; Swamy, MNS (1992), Graphs: Theory and Algorithms , John Wiley & Sons, p. 361, ISBN  978-0-471-51356-8
  20. ↑ Cechich, Alejandra; Piattini, Mario; Vallecillo, Antonio (2003), Component-Based Software Quality: Methods and Techniques , Springer Science & Business Media, p. 105, ISBN  978-3-540-40503-0
  21. ↑ Beineke, Lowell W. ; Wilson, Robin J. (1997), Graph Connections: Relationships Between Graph Theory and Other Areas of Mathematics , Clarendon Press, p. 237 , ISBN  978-0-19-851497-8
  22. ↑ Fenton y Hill (1993 , pág. 323) . 
  23. ↑ Fenton y Hill (1993 , pág. 339) . 
  24. ↑ Cooper, C. (2008), "Enumeración asintótica de grafos de flujo de unión de predicados", Combinatoria, Probabilidad y Computación , 5 (3): 215– 226, doi : 10.1017/S0963548300001991 , S2CID 10313545 
  25. ↑ Aczel, Peter (1988), Non-well-founded sets (PDF) , CSLI Lecture Notes, vol. 14, Stanford, CA: Stanford University, Center for the Study of Language and Information, ISBN  0-937073-22-9, LCCN 87-17857 , MR 0940014 , archivado del original (PDF) el 26-03-2015  
  26. ↑ Drescher, Matthew; Vetta, Adrian (2010), "Un algoritmo de aproximación para el problema de arborescencia con máxima cobertura de hojas" , ACM Trans. Algorithms , 6 (3): 46:1–46:18, doi : 10.1145/1798596.1798599 , S2CID 13987985 .
  27. ↑ Godsil, CD ; McKay, BD (1978), "Un nuevo producto de grafos y su espectro" (PDF) , Bull. Austral. Math. Soc. , 18 (1): 21–28 , doi : 10.1017/S0004972700007760 , MR 0494910 

Lecturas adicionales

  • McMahon, Elizabeth W. (1993), "Sobre el polinomio greedoide para grafos enraizados y digrafos enraizados", Journal of Graph Theory , 17 (3): 433– 442, doi : 10.1002/jgt.3190170316
  • Gordon, Gary (2001), "Un polinomio característico para grafos con raíz y digrafos con raíz", Matemáticas Discretas , 232 ( 1–3 ): 19–33 , doi : 10.1016/S0012-365X(00)00186-2
Lecturas relacionadas
6 articulos
MatemáticasMatemáticasLas matemáticas son un campo de estudio que descubre y organiza métodos, teorías y teoremas que se desarrollan y prueban para las necesidades de la...Teoría de grafosTeoría de grafosEn matemáticas , la teoría de grafos es el estudio de los grafos , que son estructuras matemáticas utilizadas para modelar relaciones por pares ent...Gráfica (matemática discreta)Gráfica (matemática discreta)En matemáticas discretas , particularmente en teoría de grafos , un grafo es una estructura que consiste en un conjunto de objetos donde algunos pa...Vertex (graph theory)Vertex (graph theory)In discrete mathematics, and more specifically in graph theory, a vertex (plural vertices) or node is the fundamental unit of which graphs are form...Grafo dirigidoUn gráfico dirigido simple En matemáticas , y más específicamente en teoría de grafos , un grafo dirigido (o dígrafo ) es un grafo que está formado...Gráfica (matemática discreta)Gráfica (matemática discreta)En matemáticas discretas , particularmente en teoría de grafos , un grafo es una estructura que consiste en un conjunto de objetos donde algunos pa...