En la teoría de grafos , una arborescencia es un grafo dirigido en el que, para un vértice u llamado raíz y cualquier otro vértice v , hay exactamente una trayectoria dirigida de u a v . Una arborescencia es, por tanto, la forma de gráfico dirigido de un árbol enraizado , entendido aquí como un gráfico no dirigido . [1] [2]
De manera equivalente, una arborescencia es un árbol dirigido y enraizado en el que todos los bordes apuntan en dirección opuesta a la raíz; existen otras caracterizaciones equivalentes. [3] [4] Toda arborescencia es un grafo acíclico dirigido (DAG), pero no todo DAG es una arborescencia.
Una arborescencia se puede definir de manera equivalente como un dígrafo enraizado en el que el camino desde la raíz hasta cualquier otro vértice es único. [1]
Definición
El término arborescencia proviene del francés. [5] Algunos autores se oponen a ella basándose en que es engorroso deletrear. [6] Existe una gran cantidad de sinónimos de arborescencia en la teoría de grafos, incluyendo árbol enraizado dirigido [2] [6] arborescencia externa , [7] árbol externo , [8] e incluso la ramificación se utiliza para denotar el mismo concepto . [8] Algunos autores han definido el árbol enraizado como un gráfico dirigido. [9] [10] [11]
Definiciones adicionales
Además, algunos autores definen una arborescencia como un árbol dirigido en expansión de un dígrafo dado. [11] [12] Lo mismo puede decirse de algunos de sus sinónimos, especialmente ramificación . [12] Otros autores usan la ramificación para denotar un bosque de arborescencias, con la última noción definida en un sentido más amplio al comienzo de este artículo, [13] [14] pero también se encuentra una variación con ambas nociones del sabor de expansión. [11]
También es posible definir una noción útil invirtiendo todos los arcos de una arborescencia, es decir, haciendo que todos apunten a la raíz en lugar de alejarse de ella. Dichos dígrafos también se designan mediante una variedad de términos como en el árbol [15] o anti-arborescencia [16], etc. WT Tutte distingue entre los dos casos usando las frases arborescencia divergente de [alguna raíz] y arborescencia convergente a [ alguna raíz]. [17]
El número de árboles enraizados (o arborescencias) con n nodos viene dado por la secuencia:
Ver también
Referencias
- ↑ a b Gordon, Gary (1989). "Un polinomio greedoide que distingue arborescencias enraizadas" . Actas de la American Mathematical Society . 107 (2): 287. doi : 10.1090 / S0002-9939-1989-0967486-0 .
- ^ a b Stanley Gill Williamson (1985). Combinatoria para Ciencias de la Computación . Publicaciones de Courier Dover. pag. 288. ISBN 978-0-486-42076-9.
- ^ Jean-Claude Fournier (2013). Teoría y aplicaciones de gráficos: con ejercicios y problemas . John Wiley e hijos. págs. 94–95. ISBN 978-1-84821-070-7.
- ^ Jean Gallier (2011). Matemáticas discretas . Springer Science & Business Media. págs. 193-194. ISBN 978-1-4419-8046-5.
- ^ Per Hage y Frank Harary (1996). Redes de islas: 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.
- ^ a b Mehran Mesbahi; Magnus Egerstedt (2010). Métodos teóricos de grafos en redes multiagente . Prensa de la Universidad de Princeton. pag. 38. ISBN 1-4008-3535-6.
- ^ Ding-Zhu Du; Ker-I Ko; Xiaodong Hu (2011). Diseño y análisis de algoritmos de aproximación . Springer Science & Business Media. pag. 108. ISBN 978-1-4614-1701-9.
- ^ a b 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.
- ^ 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.
- ^ Kenneth Rosen (2011). Matemáticas discretas y sus aplicaciones, 7ª edición . Ciencia de McGraw-Hill. pag. 747. ISBN 978-0-07-338309-5.
- ^ a b c Alexander Schrijver (2003). Optimización combinatoria: poliedros y eficiencia . Saltador. pag. 34. ISBN 3-540-44389-4.
- ^ a b Jørgen Bang-Jensen; Gregory Z. Gutin (2008). Dígrafos: teoría, algoritmos y aplicaciones . Saltador. pag. 339. ISBN 978-1-84800-998-1.
- ^ 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.
- ^ Bernhard Korte; Jens Vygen (2012). Optimización combinatoria: teoría y algoritmos (5ª ed.). Springer Science & Business Media. pag. 18. ISBN 978-3-642-24488-9.
- ^ Kurt Mehlhorn ; Peter Sanders (2008). Algoritmos y estructuras de datos: la caja de herramientas básica (PDF) . Springer Science & Business Media. pag. 52. ISBN 978-3-540-77978-0.
- ^ Bernhard Korte; Jens Vygen (2012). Optimización combinatoria: teoría y algoritmos (5ª ed.). Springer Science & Business Media. pag. 28. ISBN 978-3-642-24488-9.
- ^ Tutte, WT (2001), Graph Theory , Cambridge University Press, págs. 126-127, ISBN 978-0-521-79489-3
enlaces externos
- Weisstein, Eric W. "Arborescence" . MathWorld .
- Weisstein, Eric W. "Árbol enraizado" . MathWorld .