Árbol (teoría de grafos)

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 16 de junio de 2020; las comprobaciones requieren 6 ediciones .

Un árbol  es un grafo acíclico conexo . [1] Conectividad significa la presencia de una ruta entre cualquier par de vértices, aciclicidad significa la ausencia de ciclos. De esto, en particular, se sigue que el número de aristas en un árbol es uno menos que el número de vértices, y hay un único camino entre cualquier par de vértices.

El bosque  es un montón de árboles.

Un árbol dirigido (dirigido)  es un dígrafo acíclico ( un gráfico dirigido que no contiene ciclos), en el que solo un vértice tiene un grado de entrada cero (no hay arcos en él), y todos los demás vértices tienen un grado de entrada de 1 (exactamente un arco conduce a ellos). Un vértice con grado de entrada cero se llama raíz del árbol, los vértices con grado de salida cero (de los que no sale ningún arco) se llaman vértices terminales u hojas . [2]

Definiciones relacionadas

  1. el nivel de la raíz del árbol es 0;
  2. el nivel de cualquier otro nodo es uno mayor que el nivel de la raíz del subárbol más cercano del árbol que contiene ese nodo.

Árbol binario

El término árbol binario (también se usa el término árbol binario) tiene varios significados:

N-árboles arios

Los árboles N-arios se definen por analogía con un árbol binario. También tienen casos dirigidos y no dirigidos, así como estructuras de datos abstractas correspondientes.

Propiedades

Conteo de árboles

para el número de árboles enraizados no isomorfos con vértices satisface la ecuación funcional . ya que el número de árboles no isomorfos con vértices se puede representar usando la lista de series para árboles con raíz: donde y son ciertas constantes, , .

Codificación de árboles

Véase también

Notas

  1. § 13. Definición de árbol // Conferencias sobre teoría de grafos / Emelichev V. A., Melnikov O. I., Sarvanov V. I., Tyshkevich R. I. - M . : Nauka, Fizmatlit, 1990. - P. 53. - 384 p. — 22.000 copias.  — ISBN 5-02-013992-0 .
  2. Alfs Berztiss. Capítulo 3. Teoría de grafos. 3.6. Árboles // Estructuras de datos = AT Berztiss. estructuras de datos. teoría y práctica. - M. : Estadísticas, 1974. - S. 131. - 10.500 ejemplares.
  3. Matemáticas discretas: algoritmos. Fórmula de Cayley (enlace inaccesible) . Consultado el 29 de octubre de 2009. Archivado desde el original el 14 de junio de 2009. 

Literatura