Á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

El grado de un vértice es el número de aristas que le inciden.

Un nodo final ( hoja , vértice terminal ) es un nodo de grado 1 (es decir, un nodo al que conduce solo una arista; en el caso de un árbol dirigido, un nodo al que solo conduce un arco y no sale ningún arco) .

Un nodo de rama es un nodo no terminal.

Un árbol con un vértice marcado se llama árbol enraizado .
- $metro$ El nivel th del árbol es el conjunto de nodos del árbol, al nivel de la raíz del árbol. $T$ $metro$
- orden parcial en los vértices: si los vértices y son diferentes y el vértice se encuentra en la cadena elemental (¡única!) que conecta la raíz con el vértice . $tu \ prec v$ $tu$ $v$ $tu$ $v$
- subárbol raíz enraizado como subgrafo . $v$ $\{v\}\taza \{w\mid v<w\}$
- En un contexto en el que se supone que un árbol tiene una raíz, se dice que un árbol sin una raíz distinguida es libre .

Nivel de nodo : la longitud de la ruta desde la raíz hasta el nodo. Se puede definir recursivamente:

el nivel de la raíz del árbol es 0; $T$
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. $T$

Un árbol de expansión ( esqueleto ) es un subgrafo de un grafo dado que contiene todos sus vértices y es un árbol. Las aristas del grafo que no están incluidas en el esqueleto se llaman cuerdas del grafo con respecto al esqueleto.

Un árbol se llama irreducible si no tiene vértices de grado 2.

Un bosque es un conjunto (generalmente ordenado) que no contiene un solo árbol que no se interseca o que contiene varios árboles que no se intersecan.
Centroide : un vértice, al eliminarlo, las dimensiones de los componentes conectados resultantes no superan (la mitad del tamaño del árbol original) ${\dfrac{n}{2))$

Árbol binario

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

Un árbol no dirigido con grados de vértice como máximo 3.
Un árbol dirigido en el que los grados salientes de los vértices (el número de aristas salientes) no supera los 2.
Una estructura de datos abstracta utilizada en la programación . Las estructuras de datos como el árbol de búsqueda binario, el montón binario , el árbol rojo-negro, el árbol AVL , el montón de Fibonacci , etc. se basan en un árbol binario.

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.

Un árbol N-ario (no dirigido) es un árbol (ordinario, no dirigido) en el que los grados de los vértices no superan N + 1.
Un árbol N-ario (dirigido) es un árbol dirigido en el que los grados salientes de los vértices (el número de aristas salientes) no excede N.

Propiedades

El árbol no tiene múltiples aristas ni bucles .
Cualquier árbol con vértices contiene una arista. Además, un gráfico conexo finito es un árbol si y solo si , donde es el número de vértices y es el número de aristas del gráfico. $norte$ $n-1$ $PA=1$ $B$ $PAGS$
Un grafo es un árbol si y sólo si dos de sus distintos vértices pueden conectarse mediante una única cadena simple .
Cualquier árbol está determinado únicamente por las distancias (la longitud de la cadena más pequeña) entre sus vértices terminales (grado 1).
Cualquier árbol es un grafo bipartito .
Cualquier árbol cuyo conjunto de vértices sea como máximo contable es un gráfico plano .
Para cualquiera de los tres vértices del árbol, los caminos entre pares de estos vértices tienen exactamente un vértice común.

Conteo de árboles

El número de árboles distintos que se pueden construir sobre vértices numerados es ( teorema de Cayley [3] ). $norte$ $n^{{n-2}}$
Función generadora

T(z)=\sum_{n=1}^{\infty}T_{n}z^{n}

para el número de árboles enraizados no isomorfos con vértices satisface la ecuación funcional

Tennesse}

norte

T(z)=z\exp \sum _{r=1}^{\infty }{\frac {1}{r}}T(z^{r})

Función generadora

t(z)=\sum_{n=1}^{\infty}t_{n}z^{n}

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:

Tennesse}

norte

t(z)=T(z)-{\frac {1}{2}}\left(T^{2}(z)-T(z^{2})\right).

Para las siguientes asintóticas es verdadera $n\to\infty$

t_{n}\sim C\alfa ^{n}/n^{5/2}

donde y son ciertas constantes, , .

C

\alfa

C=0.534948...

\alfa =2.95576...

Codificación de árboles

Un árbol se puede codificar como conjuntos de ceros y unos. Considere, por ejemplo, colocar un árbol en un avión. Partiendo de algún vértice, nos desplazaremos por las aristas del árbol, girando en cada vértice hasta la arista más cercana a la derecha y volviendo atrás en los vértices finales del árbol. Pasando a lo largo de algún borde, escribimos cuando nos movemos a lo largo del borde por primera vez y cuando nos movemos a lo largo del borde la segunda vez (en la dirección opuesta). Si es el número de aristas del árbol, luego de unos pasos volveremos al vértice original, pasando por cada arista dos veces. La secuencia resultante de longitudes y (código de árbol) permite restaurar sin ambigüedades no solo el árbol en sí , sino también su colocación en el plano. Un árbol arbitrario corresponde a varios de estos códigos. En particular, la siguiente estimación aproximada del número de árboles con vértices se deriva de este método de codificación: ${\ estilo de visualización 0}$ $una$ $metro$ $2m$ ${\ estilo de visualización 0}$ $una$ $2m$ $D$ $norte$ $t_{n}\leq T_{n}<2^{2n}$

El código de Prufer asigna a un árbol finito arbitrario con vértices una secuencia de números de a con posibles repeticiones. Por ejemplo, el árbol de la figura tiene el código Prufer (4,4,4,5). Existe una correspondencia uno a uno entre los árboles de vértices etiquetados y sus códigos Prufer. La fórmula de Cayley se deriva del código de Prüfer . $norte$ $n-2$ $una$ $norte$

El árbol se puede especificar como una cadena que contiene caracteres que marcan los nodos del árbol, así como paréntesis de apertura y cierre. Existe una correspondencia uno a uno entre los árboles y sus notaciones de corchetes lineales.

Véase también

Glosario de teoría de grafos
Bosque de conjuntos disjuntos
Lista de estructuras de datos (árboles)

Notas

↑ § 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 .
↑ 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.
↑ 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. (indefinido)

Literatura

Donald Knuth . El arte de la programación informática, vol. 1. Algoritmos Fundamentales. - 3ra ed. - M .: Williams , 2006. - T. 1. Algoritmos básicos. — 720 s. - ISBN 0-201-89683-4 .
Mineral O. Teoría de grafos. - 2ª ed. — M .: Nauka , 1980. — 336 p.
Harari F. Teoría de grafos. — M .: Mir , 1973. — 302 p.

Árbol (estructura de datos)
Árbol de búsqueda binario Árbol (teoría de grafos) estructura de árbol
Árboles binarios	árbol binario árbol en T
Árboles binarios autoequilibrados	árbol AA árbol AVL árbol rojo-negro árbol de juego árbol con multas árbol cartesiano árbol de fibonacci árbol B árbol en T
árboles B	2-3-árbol árbol B⁺ árbol B* B x -árbol árbol de la UB 2-3-4 árbol (a,b)-árbol arbol bailando
árboles de prefijo	árbol de sufijos Árbol de prefijos comprimido Árbol de búsqueda ternario
Partición binaria del espacio	árbol k-dimensional árbol de vicepresidentes
Árboles no binarios	Árbol cuádruple octárbol Octree voxel disperso árbol exponencial árbol PQ
Rompiendo el espacio	R-árbol Árbol R de Hilbert R+-árbol R*-árbol árbol X M-árbol árbol de fenwick Árbol de segmentos
Otros árboles	montón árbol de hachís árbol de los dedos árbol métrico árbol de revestimiento árbol BK Árbol de doble cadena iDistancia Árbol de corte de enlace árbol LSM
Algoritmos	Primera búsqueda en amplitud Primera búsqueda en profundidad algoritmo DSW protocolo de árbol de expansión