UNIDA 6 ARBOLES Y REDES

 

Blog: Árbol y Redes en Matemáticas Discretas

Los árboles y las redes son estructuras fundamentales en las matemáticas discretas y tiene aplicaciones en computación, ingeniería.

---

 Árboles

Un árbol es un tipo especial de grafo que cumple con las siguientes características:

• Es un grafo conexo (existe al menos un camino entre cualquier par de vértices).
• No contiene ciclos (no hay caminos cerrados).

En términos más formales, un árbol es un gráfico. $\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">yo\; </span></span></span></span>}<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">=\; </span></span></span></span><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">(\; </span></span></span></span>\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">V\; </span></span></span></span>}<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">,\; </span></span></span></span>\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">mi\; </span></span></span></span>}<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">)</span></span></span></span>$ T = (V, E) donde:

$$\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">\mid \; </span></span></span></span>}\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">mi\; </span></span></span></span>}\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">\mid \; </span></span></span></span>}<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">=\; </span></span></span></span>\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">\mid \; </span></span></span></span>}\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">V\; </span></span></span></span>}\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">\mid \; </span></span></span></span>}<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">-\; </span></span></span></span>\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">1</span></span></span></span>}$$ |E| = |V| - 1

donde $V$ es el conjunto de vértices y$\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">\; mi</span></span></span></span>}$ conjunto de artistas.

Características de los Árboles:

1. Raíz: En un árbol dirigido, un vértice especial (la raíz) actúa como punto de inicio.
2. Hojas: Son los vértices que no tienen hijos (vértices descendientes).
3. Altura del árbol: Es la longitud del camino más largo desde la raíz hasta una hoja.
4. Grado: El número de hijos de un vértice.

 

Ejemplo de Árbol:

Un árbol simple con nudos:

Propiedades:

• Raíz: $\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">A</span></span></span></span>}$ A
• Hojas: $\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">do\; </span></span></span></span>}<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">,\; </span></span></span></span>\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">re\; </span></span></span></span>}<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">,\; </span></span></span></span>\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">mi</span></span></span></span>}$ do, re, mi
• Altura: 2 (longitud del camino $\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">A\; </span></span></span></span>}<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">\to \; </span></span></span></span>\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">B\; </span></span></span></span>}<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">\to \; </span></span></span></span>\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">D</span></span></span></span>}$ A\a B\a D ).

---

Árboles con Peso

Un árbol con peso es un árbol donde las aristas tienen valores asociados llamados pesos . Estos pesos pueden representar costos, distancias, tiempos, etc.

Aplicaciones de los Árboles con Peso:

• Árboles de expansión mínima (MST - Mínima Spanning Tree): Un MST conecta todos los vértices del gráfico con el menor peso posible, sin formar ciclos.
  • Algoritmo de Kruskal: Ordena las aristas por peso y las agrega al árbol si no forman un ciclo.
  • Algoritmo de Prim: Expande el árbol seleccionando siempre la arista de menor peso que conecta a un vértice nuevo.
• Redes de comunicación: Optimización de cables en redes de telecomunicaciones.
• Diseño de rutas: Minimización de costos en sistemas de transporte.

Ejemplo de Árbol con Peso:

Un árbol con pesos asociados.





Problema: Encuentra el árbol de expansión mínima.

• Total: $\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">A\; </span></span></span></span>}<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">\to \; </span></span></span></span>\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">B\; </span></span></span></span>}<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">(\; </span></span></span></span>\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">3\; </span></span></span></span>}<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">)\; </span></span></span></span><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">+\; </span></span></span></span>\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">B\; </span></span></span></span>}<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">\to \; </span></span></span></span>\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">D\; </span></span></span></span>}<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">(\; </span></span></span></span>\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">2\; </span></span></span></span>}<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">)\; </span></span></span></span><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">+\; </span></span></span></span>\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">B\; </span></span></span></span>}<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">\to \; </span></span></span></span>\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">mi\; </span></span></span></span>}<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">(\; </span></span></span></span>\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">4\; </span></span></span></span>}<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">)\; </span></span></span></span><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">+\; </span></span></span></span>\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">A\; </span></span></span></span>}<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">\to \; </span></span></span></span>\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">do\; </span></span></span></span>}<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">(\; </span></span></span></span>\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">5\; </span></span></span></span>}<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">)\; </span></span></span></span><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">=\; </span></span></span></span>\mathrm{<span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;"><span\; style="vertical-align:\; inherit;">14</span></span></span></span>}$ A \a B (3) + B \a D (2) + B \a E (4) + A \a C (5) = 14

___________________________________________________________________________________

¿Qué es una Red?

Una red es una estructura que modela un conjunto de elementos (nodos) conectados por relaciones (aristas). Matemáticamente, se representa como un gráfico o grafos.

Tipos de Redes

1. Redes Dirigidas: Las aristas tienen una dirección específica (ejemplo: flujo de tráfico).
2. Redes No Dirigidas: Las conexiones no tienen dirección (ejemplo: redes sociales).
3. Redes Ponderadas: Las aristas tienen un peso asociado (ejemplo: redes de transporte).

---

Relación entre Árboles y Redes

1. Un árbol es un caso especial de rojo.
2. Los algoritmos diseñados para árboles (como búsqueda en profundidad o amplitud) pueden extenderse para trabajar en redes más complejas.
3. Las redes ponderadas pueden contener árboles generadores mínimos que optimizan la conexión entre nodos.

---

Algunas aplicaciones de Árboles, Árboles con Peso y Redes

 Computación y Ciencias de Datos

• Representación de estructuras jerárquicas como XML o JSON.
• Optimización de bases de datos con índices basados ​​en árboles binarios.

Redes de Transporte y Logística

• Optimización de rutas mediante árboles con peso.
• Modelado de redes de carreteras o sistemas de metro.

Telecomunicaciones

• Diseño de redes óptimas para transmisión de datos.
• Detección de cuellos de botella en sistemas de comunicación.

Inteligencia artificial

• Uso de árboles de decisión para clasificar datos.
• Representación de estados y decisiones en algoritmos de búsqueda.

 Biología y ecología

• Modelado de relaciones filogenéticas mediante árboles.
• Representación de ecosistemas como redes tróficas.

---

Ejemplo de una aplicación:

Problema: Diseñar una red de fibra óptica para conectar 5 ciudades con el menor costo posible.

1. Representar las ciudades como nodos y las conexiones posibles como aristas ponderadas (costos).
2. Utilizar el algoritmo de Prim o Kruskal para encontrar el árbol generador mínimo.
3. La solución será la red más económica que conectará todas las ciudades sin redundancias.

Aquí acabo mi unidad 6.>< Paola Erika Cabrera Rojas