stringtranslate.com

Arborescencia (teoría de grafos)

En teoría de grafos , una arborescencia es un grafo dirigido donde existe un vértice r (llamado raíz ) tal que, para cualquier otro vértice v , hay exactamente un recorrido dirigido desde r hasta v (teniendo en cuenta que la raíz r es única). [1] Una arborescencia es, por tanto, la forma de grafo dirigido de un árbol con raíz , entendido aquí como un grafo no dirigido . [2] [3] Una arborescencia es también un árbol con raíz dirigido en el que todos los bordes apuntan en dirección opuesta a la raíz; existen otras caracterizaciones equivalentes. [4] [5]

Cada arborescencia es un gráfico acíclico dirigido (DAG), pero no todo DAG es una arborescencia.

Definición

El término arborescencia proviene del francés. [6] Algunos autores se oponen a él por considerar que es complicado de escribir. [7] Hay una gran cantidad de sinónimos para arborescencia en la teoría de grafos, incluidos árbol con raíces dirigidas , [3] [7] arborescencia externa , [8] árbol externo , [9] e incluso ramificación que se utilizan para denotar el mismo concepto. [9] Algunos autores han definido el árbol con raíces como un grafo dirigido. [10] [11] [12]

Otras definiciones

Además, algunos autores definen una arborescencia como un árbol dirigido que abarca un dígrafo dado. [12] [13] Lo mismo puede decirse de algunos de sus sinónimos, especialmente ramificación . [13] Otros autores usan ramificación para denotar un bosque de arborescencias, con esta última noción definida en un sentido más amplio al comienzo de este artículo, [14] [15] pero también se encuentra una variación con ambas nociones del sabor de expansión. [12]

También es posible definir una noción útil invirtiendo todos los bordes de una arborescencia, es decir, haciendo que todos apunten en la dirección de la raíz en lugar de alejarse de ella. Estos dígrafos también se designan con una variedad de términos, como dentro del árbol [16] o antiarborescencia [17] . WT Tutte distingue entre los dos casos utilizando las frases arborescencia que diverge de [alguna raíz] y arborescencia que converge hacia [alguna raíz]. [18]

El número de árboles enraizados (o arborescencias) con n nodos viene dado por la secuencia:

0, 1, 1, 2, 4, 9, 20, 48, 115, 286, 719, 1842, 4766, 12486, ... (secuencia A000081 en la OEIS ).

Véase también

Referencias

  1. ^ Darij Grinberg (2 de agosto de 2023). "Introducción a la teoría de grafos (Texto para Matemáticas 530 en la primavera de 2022 en la Universidad de Drexel)" (PDF) . Darij Grinberg, Ludwig-Maximilians-Universität München . p. 187 . Consultado el 2 de julio de 2024 . Teorema 5.6.5, enunciado A4: Para cada vértice v ∈ V, el multidígrafo D tiene un recorrido único de r a v.
  2. ^ Gordon, Gary (1989). "Un polinomio greedoide que distingue arborescencias enraizadas". Actas de la American Mathematical Society . 107 (2): 287–298. doi : 10.1090/S0002-9939-1989-0967486-0 .
  3. ^ de Stanley Gill Williamson (1985). Combinatoria para la informática . Courier Dover Publications. pág. 288. ISBN 978-0-486-42076-9.
  4. ^ Jean-Claude Fournier (2013). Teoría de grafos y aplicaciones: con ejercicios y problemas . John Wiley & Sons. págs. 94-95. ISBN 978-1-84821-070-7.
  5. ^ Jean Gallier (2011). Matemáticas discretas . Springer Science & Business Media. Págs. 193-194. ISBN. 978-1-4419-8046-5.
  6. ^ Per Hage y Frank Harary (1996). Redes de islas: comunicación, parentesco y estructuras de clasificación en Oceanía . Cambridge University Press. pág. 43. ISBN 978-0-521-55232-5.
  7. ^ ab Mehran Mesbahi; Magnus Egerstedt (2010). Métodos de teoría de grafos en redes multiagente . Princeton University Press. pág. 38. ISBN 978-1-4008-3535-5.
  8. ^ Ding-Zhu Du; Ker-I Ko; Xiaodong Hu (2011). Diseño y análisis de algoritmos de aproximación . Springer Science & Business Media. pág. 108. ISBN 978-1-4614-1701-9.
  9. ^ de Jonathan L. Gross; Jay Yellen; Ping Zhang (2013). Manual de teoría de grafos, segunda edición . CRC Press. pág. 116. ISBN 978-1-4398-8018-0.
  10. ^ David Makinson (2012). Conjuntos, lógica y matemáticas para la informática . Springer Science & Business Media. págs. 167-168. ISBN 978-1-4471-2499-3.
  11. ^ Kenneth Rosen (2011). Matemática discreta y sus aplicaciones, 7.ª edición . McGraw-Hill Science. pág. 747. ISBN 978-0-07-338309-5.
  12. ^ abc Alexander Schrijver (2003). Optimización combinatoria: poliedros y eficiencia . Springer. pág. 34. ISBN 3-540-44389-4.
  13. ^ por Jørgen Bang-Jensen; Gregory Z. Gutin (2008). Dígrafos: teoría, algoritmos y aplicaciones . Springer. pág. 339. ISBN 978-1-84800-998-1.
  14. ^ James Evans (1992). Algoritmos de optimización para redes y gráficos, segunda edición . CRC Press. pág. 59. ISBN 978-0-8247-8602-1.
  15. ^ Bernhard Korte ; Jens Vygen (2012). Optimización combinatoria: teoría y algoritmos (5.ª ed.). Springer Science & Business Media. pág. 18. ISBN 978-3-642-24488-9.
  16. ^ Kurt Mehlhorn ; Peter Sanders (2008). Algoritmos y estructuras de datos: la caja de herramientas básica (PDF) . Springer Science & Business Media. pág. 52. ISBN 978-3-540-77978-0.
  17. ^ Bernhard Korte ; Jens Vygen (2012). Optimización combinatoria: teoría y algoritmos (5.ª ed.). Springer Science & Business Media. pág. 28. ISBN 978-3-642-24488-9.
  18. ^ Tutte, WT (2001), Teoría de grafos , Cambridge University Press, págs. 126-127, ISBN 978-0-521-79489-3

Enlaces externos