in

Árbol y bosque de teoría de grafos

tree and forest1

1. ¿Qué es árbol y bosque?

Árbol

  • En teoría de grafos, un árbol es un gráfico no dirigido, conectado y acíclico. En otras palabras, un gráfico conectado que no contiene ni un solo ciclo se llama árbol.
  • Un árbol representa la estructura jerárquica en forma gráfica.
  • Los elementos de los árboles se llaman sus nodos y los bordes del árbol se llaman ramas.
  • Un árbol con n vértices tiene (n-1) aristas.
  • Los árboles proporcionan muchas aplicaciones útiles tan simples como un árbol genealógico hasta tan complejas como los árboles en las estructuras de datos de la informática.
  • A hoja en un árbol hay un vértice de grado 1 o cualquier vértice que no tenga hijos se llama hoja.

Ejemplo

Árbol y bosque

En el ejemplo anterior, todos son árboles con menos de 6 vértices.

bosque

En teoría de grafos, un bosque es un gráfico acíclico no dirigido, desconectado. En otras palabras, una colección desarticulada de árboles se conoce como bosque. Cada componente de un bosque es un árbol.

Ejemplo

Árbol y bosque

El gráfico anterior parece dos subgráficos, pero es un solo gráfico desconectado. No hay ciclos en el gráfico anterior. Por tanto, es un bosque.


2. Propiedades de los árboles

  1. Todo árbol que tenga al menos dos vértices debe tener al menos dos hojas.
  2. Los árboles tienen muchas caracterizaciones:
    Sea T una gráfica con n vértices, entonces las siguientes afirmaciones son equivalentes:
    • T es un árbol.
    • T no contiene ciclos y tiene n-1 aristas.
    • T está conectado y tiene (n -1) borde.
    • T es un gráfico conectado y cada borde es un borde de corte.
    • Dos vértices cualesquiera del gráfico T están conectados por exactamente un camino.
    • T no contiene ciclos, y para cualquier borde nuevo e, el gráfico T + e tiene exactamente un ciclo.
  3. Cada borde de un árbol está cortado.
  4. Agregar un borde a un árbol define exactamente un ciclo.
  5. Cada gráfico conectado contiene un árbol de expansión.
  6. Cada árbol tiene al menos dos vértices de grado dos.

3. Árbol de expansión

A árbol de expansión en un gráfico conectado, G es un subgráfico H de G que incluye todos los vértices de G y también es un árbol.

Ejemplo

Considere el siguiente gráfico G:

Árbol y bosque

A partir del gráfico G anterior, podemos implementar los siguientes tres árboles de expansión H:

Árbol y bosque

Métodos para encontrar el árbol de expansión

Podemos encontrar el árbol de expansión de forma sistemática utilizando cualquiera de dos métodos:

  1. Método de reducción
  2. Método de construcción

1. Método de reducción

  • Comience a elegir cualquier ciclo en el Gráfico G.
  • Retire uno de los bordes del ciclo.
  • Repita este proceso hasta que no queden ciclos.

Ejemplo

Árbol y bosque

  • Si eliminamos el borde ac que destruye el ciclo adca en el gráfico anterior, obtenemos el siguiente gráfico:

Árbol y bosque

  • Elimine el borde cb, que destruye el ciclo adcba del gráfico anterior, luego obtenemos el siguiente gráfico:

Árbol y bosque

  • Si eliminamos el borde ec, que destruye el ciclo decd del gráfico anterior, obtenemos el siguiente árbol de expansión:

Árbol y bosque

2. Método de construcción

  • Seleccione los bordes del gráfico G uno a la vez. De tal manera que no se creen ciclos.
  • Repite este proceso hasta que se incluyan todos los vértices.

Ejemplo

Considere el siguiente gráfico G,

Árbol y bosque

Árbol y bosque

Árbol y bosque

  • Después de eso, elige el borde CE,

Árbol y bosque

  • A continuación, elija el borde cb, finalmente obtenemos el siguiente árbol de expansión:

Árbol y bosque

Rango de circuito

El número de aristas que debemos eliminar de G para obtener un árbol de expansión.

Árbol de expansión G = m- (n-1), que se llama rango de circuito de G.

Ejemplo

Árbol y bosque

En el gráfico anterior, aristas m = 7 y vértices n = 5

Entonces el rango del circuito es,

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

1632969808 753 img json

Que es JSON

paper clip

Medición de la longitud al cuarto o media pulgada más cercano