Árbol (teoría de grafos) - Tree (graph theory)

Árboles
Tree graph.svg
Un árbol etiquetado con 6 vértices y 5 aristas.
Vértices v
Bordes v  - 1
Número cromático 2 si v > 1
Tabla de gráficos y parámetros

En la teoría de grafos , un árbol es un grafo no dirigido en el que dos vértices cualesquiera están conectados por exactamente una ruta , o equivalentemente un grafo no dirigido acíclico conectado . Un bosque es un grafo no dirigido en el que dos vértices cualesquiera están conectados por como máximo un camino, o lo que es lo mismo, un grafo no dirigido acíclico, o lo que es lo mismo, una unión disjunta de árboles.

A poliárbol (o árbol dirigido o árbol orientado o red individualmente conectado ) es un gráfico dirigido acíclico (DAG) cuyo subyacente grafo no dirigido es un árbol. A polyforest (o bosque dirigida o forestal orientada a ) es un gráfico acíclico dirigido cuyo subyacente grafo no dirigido es un bosque.

Los diversos tipos de estructuras de datos a los que se hace referencia como árboles en informática tienen gráficos subyacentes que son árboles en la teoría de gráficos, aunque tales estructuras de datos son generalmente árboles con raíces . Un árbol enraizado puede ser dirigido, llamado árbol enraizado dirigido , ya sea haciendo que todos sus bordes apunten en dirección opuesta a la raíz, en cuyo caso se llama arborescencia o árbol exterior, o haciendo que todos sus bordes apunten hacia la raíz, en cuyo caso se llama anti-arborescencia o en árbol . Algunos autores han definido un árbol enraizado en sí mismo como un gráfico dirigido. Un bosque enraizado es una unión inconexa de árboles enraizados. Un bosque enraizado puede ser dirigido, llamado bosque enraizado dirigido , ya sea haciendo que todos sus bordes apunten en dirección opuesta a la raíz de cada árbol enraizado, en cuyo caso se le llama ramificación o bosque externo , o haciendo que todos sus bordes apunten hacia la raíz. en cada árbol enraizado, en cuyo caso se denomina anti-ramificación o en el bosque .

El término "árbol" fue acuñado en 1857 por el matemático británico Arthur Cayley .

Definiciones

Árbol

Un árbol es un gráfico G no dirigido que satisface cualquiera de las siguientes condiciones equivalentes:

  • G está conectado y es acíclico (no contiene ciclos).
  • G es acíclico, y se forma un ciclo simple si cualquier borde se añade a G .
  • G está conectado, pero sería desconectado si cualquier borde solo se elimina de G .
  • G está conectado y el 3-vértice gráfico completo K 3 no es un menor de G .
  • Cualquiera de los dos vértices de G se pueden conectar mediante una ruta simple única .

Si G tiene un número finito de vértices, digamos n de ellos, entonces las declaraciones anteriores también son equivalentes a cualquiera de las siguientes condiciones:

  • G está conectado y tiene n - 1 aristas.
  • G está conectado, y cada subgrafo de G incluye al menos un vértice con cero o una arista incidente. (Es decir, G está conectado y 1-degenerado ).
  • G no tiene ciclos simples y tiene n - 1 aristas.

Como en otras partes de la teoría de grafos, el grafo de orden cero (grafo sin vértices) generalmente no se considera un árbol: si bien está conectado de forma vacía como un grafo (dos vértices cualesquiera pueden estar conectados por una ruta), no es 0 -conectado (o incluso (-1) -conectado) en topología algebraica, a diferencia de los árboles no vacíos, y viola la relación "un vértice más que bordes". Sin embargo, puede considerarse como un bosque que consta de cero árboles.

Un vértice interno (o vértice interior o vértice rama ) es un vértice de grado al menos 2. De manera similar, un vértice externo (o vértice exterior , vértice terminal de o de la hoja ) es un vértice de grado 1.

Un árbol irreducible (o árbol de serie reducida ) es un árbol en el que no hay vértice de grado 2 (enumerado en la secuencia A000014 en la OEIS ).

bosque

Un bosque es un gráfico no dirigido en el que dos vértices cualesquiera están conectados por un camino como máximo. De manera equivalente, un bosque es un gráfico acíclico no dirigido, cuyos componentes conectados son árboles; en otras palabras, el gráfico consiste en una unión disjunta de árboles. Como casos especiales, el gráfico de orden cero (un bosque que consta de cero árboles), un solo árbol y un gráfico sin bordes son ejemplos de bosques. Dado que para cada árbol V - E = 1 , podemos contar fácilmente el número de árboles que hay dentro de un bosque restando la diferencia entre los vértices totales y los bordes totales. TV - TE = número de árboles en un bosque .

Polytree

Artículo principal: Polytree

A poliárbol (o árbol dirigido o árbol orientado o red individualmente conectado ) es un gráfico dirigido acíclico (DAG) cuyo subyacente grafo no dirigido es un árbol. En otras palabras, si reemplazamos sus bordes dirigidos con bordes no dirigidos, obtenemos un gráfico no dirigido que está conectado y es acíclico.

Algunos autores restringen la frase "árbol dirigido" al caso en el que las aristas están todas dirigidas hacia un vértice particular, o todas alejadas de un vértice particular (ver arborescencia ).

Polyforest

A polyforest (o bosque dirigida o forestal orientada a ) es un gráfico acíclico dirigido cuyo subyacente grafo no dirigido es un bosque. En otras palabras, si reemplazamos sus bordes dirigidos con bordes no dirigidos, obtenemos un gráfico no dirigido que es acíclico.

Algunos autores restringen la frase "bosque dirigido" al caso donde los bordes de cada componente conectado están todos dirigidos hacia un vértice particular, o todos dirigidos lejos de un vértice particular (ver ramificación ).

Árbol enraizado

Un árbol enraizado es un árbol en el que un vértice se ha designado como raíz . A los bordes de un árbol enraizado se les puede asignar una orientación natural, ya sea hacia afuera o hacia la raíz, en cuyo caso la estructura se convierte en un árbol enraizado dirigido . Cuando un árbol enraizado dirigido tiene una orientación alejada de la raíz, se llama arborescencia o árbol externo ; cuando tiene una orientación hacia la raíz, se denomina anti-arborescencia o in-tree . El orden de los árboles es el orden parcial en los vértices de un árbol con u < v si y solo si la ruta única desde la raíz hasta v pasa por u . Un árbol enraizado T que es un subgrafo de algún gráfico G es un árbol normal si los extremos de cada camino T en G son comparables en este orden de árbol ( Diestel 2005 , p. 15). Los árboles enraizados, a menudo con una estructura adicional como el orden de los vecinos en cada vértice, son una estructura de datos clave en la informática; ver estructura de datos de árbol .

En un contexto en el que los árboles suelen tener una raíz, un árbol sin ninguna raíz designada se denomina árbol libre .

Un árbol etiquetado es un árbol en el que a cada vértice se le asigna una etiqueta única. Los vértices de un árbol etiquetado en n vértices normalmente reciben las etiquetas 1, 2, ..., n . Un árbol recursivo es un árbol con raíz etiquetado donde las etiquetas de los vértices respetan el orden del árbol (es decir, si u < v para dos vértices u y v , entonces la etiqueta de u es más pequeña que la etiqueta de v ).

En un árbol enraizado, el padre de un vértice v es el vértice conectado av en el camino a la raíz; cada vértice tiene un padre único excepto la raíz que no tiene padre. Un hijo de un vértice v es un vértice del cual v es el padre. Un ascendente de un vértice v es cualquier vértice que es el padre de v o es (recursivamente) el ascendente del padre de v . Un descendiente de un vértice v es cualquier vértice que es hijo de v o es (recursivamente) descendiente de cualquiera de los hijos de v . Un hermano de un vértice v es cualquier otro vértice del árbol que tiene el mismo padre que v . Una hoja es un vértice sin hijos. Un vértice interno es un vértice que no es una hoja.

La altura de un vértice en un árbol enraizado es la longitud del camino descendente más largo hasta una hoja desde ese vértice. La altura del árbol es la altura de la raíz. La profundidad de un vértice es la longitud de la ruta hasta su raíz ( ruta raíz ). Esto es comúnmente necesario en la manipulación de varios árboles autoequilibrados, árboles AVL en particular. La raíz tiene una profundidad de cero, las hojas tienen una altura de cero y un árbol con un solo vértice (por lo tanto, una raíz y una hoja) tiene una profundidad y una altura de cero. Convencionalmente, un árbol vacío (un árbol sin vértices, si está permitido) tiene profundidad y altura -1.

Un árbol k-ario es un árbol enraizado en el que cada vértice tiene como máximo k hijos. Los árboles de 2 arios a menudo se denominan árboles binarios , mientras que los árboles de 3 arios a veces se denominan árboles ternarios .

Árbol ordenado

Un árbol ordenado (o árbol plano ) es un árbol enraizado en el que se especifica un orden para los hijos de cada vértice. A esto se le llama "árbol plano" porque una ordenación de los hijos equivale a una incrustación del árbol en el plano, con la raíz en la parte superior y los hijos de cada vértice más abajo que ese vértice. Dada una incrustación de un árbol enraizado en el plano, si uno fija la dirección de los niños, digamos de izquierda a derecha, entonces una incrustación da un orden de los niños. Por el contrario, dado un árbol ordenado y dibujando convencionalmente la raíz en la parte superior, los vértices secundarios de un árbol ordenado se pueden dibujar de izquierda a derecha, lo que produce una incrustación plana esencialmente única.

Propiedades

  • Cada árbol es un gráfico bipartito . Un gráfico es bipartito si y solo si no contiene ciclos de longitud impar. Dado que un árbol no contiene ciclos, es bipartito.
  • Cada árbol es un gráfico de mediana .
  • Cada árbol con solo un número numerable de vértices es un gráfico plano .
  • Cada gráfico conectado G admite un árbol de expansión , que es un árbol que contiene cada vértice de G y cuyos bordes son bordes de G .
  • Cada grafo conectado con solo un número numerable de vértices admite un árbol de expansión normal ( Diestel 2005 , Prop. 8.2.4).
  • Existen grafos conectados con incontables vértices que no admiten un árbol de expansión normal ( Diestel 2005 , Prop. 8.5.2).
  • Todo árbol finito con n vértices, con n > 1 , tiene al menos dos vértices terminales (hojas). Este número mínimo de hojas es característico de los gráficos de trayectoria ; el número máximo, n - 1 , se obtiene sólo mediante gráficas de estrellas . El número de hojas es al menos el grado máximo de vértice.
  • Para cualesquiera tres vértices en un árbol, los tres caminos entre ellos tienen exactamente un vértice en común (este vértice se llama la mediana de estos tres vértices).
  • Cada árbol tiene un centro que consta de un vértice o dos vértices adyacentes. El centro es el vértice del medio o los dos vértices del medio en cada camino más largo. De manera similar, cada árbol de n- vértices tiene un centroide que consta de un vértice o dos vértices adyacentes. En el primer caso, la eliminación del vértice divide el árbol en subárboles de menos de n / 2 vértices. En el segundo caso, la eliminación del borde entre los dos vértices centroidales divide el árbol en dos subárboles de exactamente n / 2 vértices.

Enumeración

Árboles etiquetados

La fórmula de Cayley establece que hay n n -2 árboles en n vértices etiquetados. Una demostración clásica usa secuencias de Prüfer , que naturalmente muestran un resultado más fuerte: el número de árboles con vértices 1, 2, ..., n de grados d 1 , d 2 , ..., d n respectivamente, es el coeficiente multinomial

Un problema más general es contar árboles de expansión en un gráfico no dirigido , que se aborda en el teorema del árbol de matrices . (La fórmula de Cayley es el caso especial de árboles de expansión en un gráfico completo .) El problema similar de contar todos los subárboles independientemente del tamaño es # P-completo en el caso general ( Jerrum (1994) ).

Árboles sin etiquetar

Contar el número de árboles libres sin etiquetar es un problema más complicado. No se conoce una fórmula cerrada para el número t ( n ) de árboles con n vértices hasta el isomorfismo de la gráfica . Los primeros valores de t ( n ) son

1, 1, 1, 1, 2, 3, 6, 11, 23, 47, 106, 235, 551, 1301, 3159,… (secuencia A000055 en la OEIS ).

Otter (1948) demostró la estimación asintótica

con los valores C y α conocidos como aproximadamente 0.534949606 ... y 2.95576528565 ... (secuencia A051491 en la OEIS ), respectivamente. (Aquí, f ~ g significa que lim n → ∞ f / g = 1. ) Esto es una consecuencia de su estimación asintótica para el número r ( n ) de árboles con raíces no etiquetadas con n vértices:

con D alrededor de 0,43992401257 ... y el mismo α que el anterior (cf. Knuth (1997) , cap. 2.3.4.4 y Flajolet & Sedgewick (2009) , cap. VII.5, p. 475).

Los primeros valores de r ( n ) son

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

Tipos de arboles

  • Un gráfico de trayectoria (o gráfico lineal ) consta de n vértices dispuestos en una línea, de modo que los vértices i e i +1 están conectados por una arista para i = 1, ..., n −1.
  • Un árbol con forma de estrella consta de un vértice central llamado raíz y varios gráficos de ruta adjuntos. Más formalmente, un árbol es parecido a una estrella si tiene exactamente un vértice de grado mayor que 2.
  • Un árbol estrella es un árbol que consta de un solo vértice interno (y n −1 hojas). En otras palabras, un árbol estelar de orden n es un árbol de orden n con tantas hojas como sea posible.
  • Un árbol de oruga es un árbol en el que todos los vértices están dentro de la distancia 1 de un subgrafo de ruta central.
  • Un árbol de langosta es un árbol en el que todos los vértices están dentro de la distancia 2 de un subgráfico de ruta central.
  • Un árbol regular de grado d es el árbol infinito con d aristas en cada vértice. Estos surgen como los gráficos de Cayley de grupos libres y en la teoría de los edificios de Tits .

Ver también

Notas

Referencias

Otras lecturas