stringtranslate.com

Arborescencia (teoría de grafos)

En teoría de grafos , una arborescencia es un gráfico dirigido donde existe un vértice r (llamado raíz ) tal que, para cualquier otro vértice v , hay exactamente un recorrido dirigido desde v hasta r (observando que la raíz r es única). [1] Una arborescencia es, por tanto, la forma de gráfico dirigido de un árbol enraizado , entendido aquí como un gráfico no dirigido . [2] [3] Una arborescencia también es un árbol con raíces dirigidas 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 ello alegando que es complicado de escribir. [7] Existe una gran cantidad de sinónimos de arborescencia en la teoría de grafos, incluido árbol con raíces dirigidas , [3] [7] arborescencia externa , [8] árbol externo , [9] e incluso se usa ramificación para denotar lo mismo. concepto. [9] Algunos autores han definido el propio árbol enraizado como un gráfico dirigido. [10] [11] [12]

Otras definiciones

Además, algunos autores definen una arborescencia como un árbol dirigido de expansión de un dígrafo determinado. [12] [13] Lo mismo puede decirse de algunos de sus sinónimos, especialmente ramificación . [13] Otros autores utilizan la ramificación para denotar un bosque de arborescencias, y esta última noción se define 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 que se extiende. [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 mediante una variedad de términos, como in-tree [16] o anti-arborescencia . [17] WT Tutte distingue entre los dos casos utilizando las frases arborescencia que diverge de [alguna raíz] y arborescencia que converge a [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 el OEIS ).

Ver también

Referencias

  1. ^ Darij Grinberg (2 de agosto de 2023). "Una 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, Universidad Ludwig-Maximilians de Múnich . pag. 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 desde r hasta v.
  2. ^ Gordon, Gary (1989). "Un polinomio codicioso que distingue arborescencias enraizadas". Actas de la Sociedad Matemática Estadounidense . 107 (2): 287–298. doi : 10.1090/S0002-9939-1989-0967486-0 .
  3. ^ ab Stanley Gill Williamson (1985). Combinatoria para la Informática . Publicaciones de Courier Dover. pag. 288.ISBN​ 978-0-486-42076-9.
  4. ^ Jean-Claude Fournier (2013). Teoría y aplicaciones de grafos: con ejercicios y problemas . John Wiley e hijos. págs. 94–95. ISBN 978-1-84821-070-7.
  5. ^ Jean Gallier (2011). Matemáticas discretas . Medios de ciencia y negocios de Springer. págs. 193-194. ISBN 978-1-4419-8046-5.
  6. ^ Por Hage y Frank Harary (1996). Redes insulares: estructuras de comunicación, parentesco y clasificación en Oceanía . Prensa de la Universidad de Cambridge. pag. 43.ISBN​ 978-0-521-55232-5.
  7. ^ ab Mehran Mesbahi; Magnus Egerstedt (2010). Métodos de teoría de grafos en redes multiagente . Prensa de la Universidad de Princeton. pag. 38.ISBN​ 978-1-4008-3535-5.
  8. ^ Ding-Zhu Du; Ker-I Ko; Xiao Dong Hu (2011). Diseño y Análisis de Algoritmos de Aproximación . Medios de ciencia y negocios de Springer. pag. 108.ISBN​ 978-1-4614-1701-9.
  9. ^ ab Jonathan L. Gross; Jay Yellen; Ping Zhang (2013). Manual de teoría de grafos, segunda edición . Prensa CRC. pag. 116.ISBN​ 978-1-4398-8018-0.
  10. ^ David Makinson (2012). Conjuntos, Lógica y Matemáticas para la Computación . Medios de ciencia y negocios de Springer. págs. 167-168. ISBN 978-1-4471-2499-3.
  11. ^ Kenneth Rosen (2011). Matemática discreta y sus aplicaciones, 7ª edición . Ciencia McGraw-Hill. pag. 747.ISBN​ 978-0-07-338309-5.
  12. ^ abc Alexander Schrijver (2003). Optimización combinatoria: poliedros y eficiencia . Saltador. pag. 34.ISBN​ 3-540-44389-4.
  13. ^ ab Jørgen Bang-Jensen; Gregorio Z. Gutin (2008). Dígrafos: Teoría, Algoritmos y Aplicaciones . Saltador. pag. 339.ISBN​ 978-1-84800-998-1.
  14. ^ James Evans (1992). Algoritmos de optimización para redes y gráficos, segunda edición . Prensa CRC. pag. 59.ISBN​ 978-0-8247-8602-1.
  15. ^ Bernhard Korte ; Jens Vygen (2012). Optimización combinatoria: teoría y algoritmos (5ª ed.). Medios de ciencia y negocios de Springer. pag. 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) . Medios de ciencia y negocios de Springer. pag. 52.ISBN​ 978-3-540-77978-0.
  17. ^ Bernhard Korte ; Jens Vygen (2012). Optimización combinatoria: teoría y algoritmos (5ª ed.). Medios de ciencia y negocios de Springer. pag. 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